Skip to content

Roadmap #1

@isPANN

Description

@isPANN

Roadmap: NP-Hard Problems & Reductions

Current State (17 problems, 20 reduction edges)

Category Problems Count
Graph IndependentSet, MaximalIS, VertexCover, DominatingSet, KColoring, MaxCut, Matching, Clique 8
Satisfiability SAT, KSatisfiability, CircuitSAT 3
Set SetCovering, SetPacking 2
Optimization SpinGlass, QUBO, ILP 3
Specialized Factoring, BicliqueCover, BMF, PaintShop 4

Current reduction graph: SAT → {KSat, IS, DominatingSet, 3-Coloring}, VC ↔ IS ↔ SetPacking, VC → SetCover, Matching → SetPacking, SpinGlass ↔ MaxCut, SpinGlass ↔ QUBO, ILP → QUBO, CircuitSAT → SpinGlass, Factoring → {CircuitSAT, ILP}, plus several → QUBO and → ILP edges.


Tier 1: Karp's 21 NP-Complete Problems (1972)

The foundational set. Items marked ✅ are already implemented; the rest are new targets.

Karp's reduction tree (from Karp 1972):

SAT ✅
├─ 0-1 Integer Programming ✅ (ILP)
├─ Clique ✅ ─── Vertex Cover ✅ ── Independent Set ✅
├─ Set Packing ✅
├─ Set Covering ✅
├─ 3-SAT ✅ (KSatisfiability)
├─ Chromatic Number ✅ (KColoring)
├─ Clique Cover
├─ Exact Cover
├─ Hitting Set
├─ Steiner Tree
├─ 3-Dimensional Matching
├─ Knapsack (0-1)
├─ Subset Sum
├─ Partition
├─ Hamiltonian Circuit
├─ Directed Hamiltonian Circuit
├─ Feedback Node Set
├─ Feedback Arc Set
└─ Job Sequencing (with integer lengths)

Status: 12/21 done. 9 remaining.

# Problem Status Canonical Reduction From Reference
1 SAT Cook's theorem Karp [LO1]
2 0-1 Integer Programming ✅ (ILP) SAT Karp [MP1]
3 Clique SAT / 3-SAT Karp [GT19]
4 Set Packing Exact Cover Karp [SP3]
5 Vertex Cover Clique (complement) Karp [GT1]
6 Set Covering Vertex Cover / Exact Cover Karp [SP5]
7 Feedback Node Set SAT Karp [GT7]
8 Feedback Arc Set SAT Karp [GT8]
9 Directed Hamiltonian Circuit Vertex Cover Karp [GT38]
10 Undirected Hamiltonian Circuit Directed HC Karp [GT37]
11 3-SAT ✅ (KSatisfiability) SAT Karp [LO2]
12 Chromatic Number ✅ (KColoring) SAT / 3-SAT Karp [GT4]
13 Clique Cover Chromatic Number (complement) Karp [GT17]
14 Exact Cover 3-Dimensional Matching Karp [SP2]
15 Hitting Set Vertex Cover (dual of Set Cover) Karp [SP8]
16 Steiner Tree Exact Cover Karp [ND12]
17 3-Dimensional Matching SAT / 3-SAT Karp [SP1]
18 Knapsack (0-1) Subset Sum Karp [MP9]
19 Job Sequencing Partition Karp [SS1]
20 Partition 3-Dimensional Matching Karp [SP12]
21 Subset Sum Partition / 3-SAT (CLRS) Karp [SP13]

Tier 2: Core Extensions (from Garey & Johnson / CLRS / Lucas 2014)

Problems that are extremely common in textbooks, applications, and quantum computing (QUBO/Ising).

# Problem Canonical Reduction From Why Important Reference
22 TSP (decision) Hamiltonian Cycle Iconic NP-hard problem G&J [ND22]
23 Bin Packing Partition Scheduling, resource allocation G&J [SR1]
24 3-Partition 3-Dimensional Matching Strongly NP-complete G&J [SP15]
25 Graph Partitioning Partition into Triangles Lucas §2.2, quantum computing G&J [ND14]
26 Max 2-SAT SAT QUBO natural formulation G&J [LO5]
27 Minimum Maximal Matching Vertex Cover Lucas §4.5 G&J [GT10]
28 Number Partitioning — (Partition variant) Lucas §2.1, QUBO natural Lucas §2.1
29 Longest Path Hamiltonian Path Fundamental graph problem G&J [ND29]
30 Dominating Set (weighted) ✅ (unweighted exists) Extending existing

Tier 3: Specialized & Application-Driven

# Problem Canonical Reduction From Why Important Reference
31 Directed Feedback Vertex Set SAT Lucas §8.3, Ising formulation G&J [GT7]
32 Minimum Feedback Edge Set SAT Lucas §8.5, Ising formulation G&J [GT9]
33 Graph Isomorphism Lucas §9, not known NP-complete Lucas §9
34 Subgraph Isomorphism Clique Pattern matching G&J [GT48]
35 Set Splitting SAT Hypergraph problems G&J [SP4]
36 Multiprocessor Scheduling Partition OS/parallel computing G&J [SS8]
37 Shortest Common Superstring Vertex Cover Bioinformatics (genome assembly) G&J [SR9]
38 Protein Folding 3-SAT Computational biology G&J [MS20]
39 Minimum Broadcast Time Network communication G&J [ND49]
40 Bandwidth 3-Partition Matrix reordering G&J [GT40]

Reduction Paths (not unique!)

Multiple textbooks prove the same NP-completeness through different chains. We should aim to implement the most useful/natural ones.

CLRS Textbook Chain

CIRCUIT-SAT → SAT → 3-SAT → CLIQUE → VERTEX-COVER → HAM-CYCLE → TSP
                         └──→ SUBSET-SUM → PARTITION → BIN-PACKING

Karp's Original Tree (key branches)

SAT → 3-DM → Exact Cover → {Steiner Tree, Set Cover, Partition → Subset Sum}
SAT → 3-DM → Partition → {Subset Sum, Multiprocessor Scheduling, Bin Packing}
SAT → 3-DM → Partition into Triangles → Graph Partitioning
SAT → Vertex Cover → {Ham Path, IS, Dom Set, Set Cover, Hitting Set}
SAT → 3-Coloring → {Partition into Cliques/Forests, Clique Cover}

Lucas 2014 — Direct Ising/QUBO Formulations

These provide direct problem → QUBO/Ising mappings (no intermediate problems):

Number Partitioning → Ising (§2.1)      Graph Partitioning → Ising (§2.2)
Maximum Clique → Ising (§2.3)           Exact Cover → Ising (§4.1)
Set Packing → Ising (§4.2)             Min Vertex Cover → Ising (§4.3)
SAT → Ising (§4.4)                     Min Maximal Matching → Ising (§4.5)
Graph Coloring → Ising (§6.1)          Clique Cover → Ising (§6.2)
Job Sequencing → Ising (§6.3)          Hamiltonian Cycle → Ising (§7.1)
Directed Feedback Vertex Set → Ising (§8.3)
Min Feedback Edge Set → Ising (§8.5)   Graph Isomorphism → Ising (§9)

Glover & Kochenberger — QUBO Tutorial Formulations

Number Partitioning → QUBO (natural)    Max-Cut → QUBO (natural)
Min Vertex Cover → QUBO (penalty)       Set Packing → QUBO (penalty)
Max 2-SAT → QUBO (penalty)             Set Partitioning → QUBO (general)
Graph Coloring → QUBO (general)

Key References

Primary (with reduction proofs)

  1. Karp (1972)Reducibility Among Combinatorial Problems — original 21 reductions
  2. Garey & Johnson (1979)Computers and Intractability — 300+ problems, the comprehensive reference
  3. CLRS (4th ed.) — Chapter 34, standard textbook reduction chain
  4. Moore & Mertens (2011)The Nature of Computation — modern treatment, reduction chains for Circuit SAT, 3-SAT, NAE-SAT, Graph Coloring, Independent Set
  5. Lucas (2014)Ising formulations of many NP problems — direct QUBO/Ising for all Karp's 21
  6. Glover & Kochenberger (2019)Tutorial on Formulating QUBO Models — practical QUBO formulations
  7. Filar & Haythorpe (2019)Linearly-growing Reductions of Karp's 21 — efficient reductions

Catalogs & Databases

  1. Crescenzi & Kann Compendium — 200+ NP optimization problems with approximability
  2. Liverpool Annotated List — 88 problems with annotations
  3. Graph of NP-Complete Reductions — 88+ problems as CSV with full reduction DAG

Tools & Implementations

  1. ProblemReductions.jl — Julia sister library (18 problems, same maintainer)
  2. GenericTensorNetworks.jl — tensor network solver using ProblemReductions.jl
  3. Karp DSL (PLDI 2022) — Racket DSL for NP reductions
  4. VisuAlgo Reductions — interactive visualization (CLRS+Karp+G&J)
  5. Fixstars Amplify — Lucas demos — runnable QUBO formulations for 14 Lucas problems
  6. SAT-based Reductions (MFCS 2024)arxiv:2511.18639 — formal verification of reductions

Metadata

Metadata

Assignees

No one assigned

    Labels

    documentationImprovements or additions to documentation

    Type

    No type
    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions