Skip to content
Tutorials Center
My learning

Topics

Lesson 47 of 59 ยท Complexity

Classic NP-Complete Problems

Meet the classic NP-complete problems and their reduction chain: 3-SAT, Clique, Independent Set, Vertex Cover, Hamiltonian cycle and TSP, with tested Python reductions.

Once SAT was shown NP-complete, the floodgates opened. In 1972 Richard Karp published a list of 21 problems that all turned out to be NP-complete, and today thousands are known. They come from graph theory, scheduling, number theory, logic, games and puzzles. The reason this matters: they are all the same problem in disguise. A fast algorithm for any one gives a fast algorithm for all.

In this lesson you will see the most famous members, how they connect through reductions, and you will run two reductions in Python and test them against brute force. Make sure you are comfortable with polynomial-time reductions and the recipe from the previous lesson: show membership in NP, then reduce a known NP-complete problem to the new one.

The reduction map

flowchart TD
    SAT["SAT"] --> S3["3-SAT"]
    S3 --> CL["CLIQUE"]
    S3 --> SS["SUBSET-SUM"]
    S3 --> HP["HAMPATH"]
    S3 --> COL["3-COLORING"]
    CL --> IS["INDEPENDENT-SET"]
    IS --> VC["VERTEX-COVER"]
    HP --> HC["HAMILTONIAN-CYCLE"]
    HC --> TSP["TRAVELING SALESMAN (decision)"]
    SS --> PART["PARTITION"]
    SS --> KS["KNAPSACK (decision)"]

One possible web of reductions. Each arrow is a polynomial-time reduction, so hardness flows along the arrows.

The catalogue

Problem Question Certificate
3-SAT Is a 3-CNF formula satisfiable? an assignment
CLIQUE Does G have k vertices, all pairwise adjacent? the k vertices
INDEPENDENT-SET Does G have k vertices, pairwise non-adjacent? the k vertices
VERTEX-COVER Is there a set of k vertices touching every edge? the k vertices
HAMILTONIAN-CYCLE Is there a cycle visiting each vertex exactly once? the cycle
TSP (decision) Is there a tour of length at most B? the tour
SUBSET-SUM Does some subset add up to t? the subset
PARTITION Can the numbers be split into two equal-sum halves? one half
KNAPSACK (decision) Can you reach value V within weight W? the chosen items
3-COLORING Can vertices be colored with 3 colors, neighbors different? the coloring
SET-COVER Can k of the given sets cover the universe? the k sets
BIN-PACKING Do the items fit in k bins of capacity C? the packing

All of them are in NP: each certificate is short and checkable in polynomial time. What is hard is finding the certificate.

From 3-SAT to CLIQUE

Take a 3-CNF formula with k clauses. Build a graph like this:

  • For each clause and each of its literals, create one vertex, so each clause contributes a group of (up to) three vertices.
  • Connect two vertices with an edge when they belong to different clauses and their literals are not contradictory (one is not the negation of the other).
  • Ask for a clique of size k.

A clique of size k picks exactly one literal from each clause (vertices in the same clause are never adjacent), and no two picked literals contradict each other. Setting those literals true gives a satisfying assignment. In the other direction, a satisfying assignment lets you pick one true literal per clause, and these pairwise-compatible literals form a clique. The graph has at most 3k vertices and 9k^2 candidate edges, so the construction is polynomial.

Python Reducing 3-SAT to CLIQUE and testing it

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Clique, Independent Set and Vertex Cover

These three are one problem seen from three angles. For a graph G with n vertices and a vertex set S:

  • S is a clique in G exactly when S is an independent set in the complement of G.
  • S is a vertex cover exactly when its complement V \ S is an independent set: every edge must touch S, so no edge can have both ends outside S.

So INDEPENDENT-SET โ‰คp VERTEX-COVER by mapping (G, k) to (G, n - k). Given any vertex cover of size n - k, the rest is an independent set of size k, and vice versa.

Hamiltonian cycle to TSP

The traveling salesman problem asks for a shortest round trip through all cities. Its decision form: given cities, distances and a budget B, is there a tour of total length at most B?

The reduction from HAMILTONIAN-CYCLE: given a graph G with n vertices, build a complete graph on the same vertices. Give an edge weight 1 if it is an edge of G and weight 2 otherwise, and set the budget B = n. A tour of cost n must use only weight-1 edges, which means it follows edges of G and visits every vertex once: a Hamiltonian cycle.

Python Hamiltonian cycle to TSP, and Vertex Cover to Independent Set

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Subtle boundaries between easy and hard

Many NP-complete problems have an easy twin that lives in P. Learning to spot the border is a useful skill.

Easy (in P) Hard (NP-complete)
2-SAT 3-SAT
Shortest path Longest simple path
Euler cycle (every edge once) Hamiltonian cycle (every vertex once)
2-coloring (bipartite check) 3-coloring
Minimum spanning tree Steiner tree
Matching in a graph 3-dimensional matching
Subset sum with small numbers (pseudo-polynomial DP) Subset sum with large numbers in binary

Pseudo-polynomial algorithms. SUBSET-SUM, PARTITION and KNAPSACK have dynamic programs that run in time proportional to the numeric value of the target. That is exponential in the number of bits, so there is no contradiction with NP-completeness. Problems with this property are called weakly NP-complete; problems like 3-SAT or CLIQUE that stay hard even for tiny numbers are strongly NP-complete.

Common mistakes

  • Reducing in the wrong direction (from the new problem to the known one).
  • Proving only that yes-instances map to yes-instances, but not the reverse.
  • Claiming NP-completeness without showing the problem is in NP.
  • Treating "optimization" and "decision" as different in difficulty. We study decision versions because they have yes/no answers, but an algorithm for the decision version of TSP can find the optimal tour length by binary search on B, so the two versions are equally hard up to polynomial factors.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In the 3-SAT to CLIQUE reduction, a k-clique picks exactly one literal from each of the k clauses because

    Edges join only vertices of different clauses, so a clique can contain at most one vertex per clause and needs k of them.
  2. 2. How does INDEPENDENT-SET reduce to VERTEX-COVER?

    S is an independent set exactly when V minus S is a vertex cover, so size k independent sets correspond to size n - k covers.
  3. 3. In the Hamiltonian cycle to TSP reduction, what budget B is used?

    Edges of G get weight 1 and non-edges weight 2. A tour of total length n uses only real edges, so it is a Hamiltonian cycle.
  4. 4. Which of these problems is known to be in P?

    2-SAT can be solved in linear time through strongly connected components, while the other three are NP-complete.
  5. 5. Why is the dynamic-programming algorithm for SUBSET-SUM not a contradiction to its NP-completeness?

    It is pseudo-polynomial: polynomial in the value of the numbers but exponential in the number of bits used to write them.

Summary

  • Karp's 21 problems started a huge catalogue of NP-complete problems; they are all polynomially equivalent.
  • 3-SAT reduces to CLIQUE by building a graph with one vertex per literal occurrence and joining compatible literals from different clauses.
  • Clique, independent set and vertex cover are tied together by complements.
  • Hamiltonian cycle reduces to TSP with weights 1 and 2 and budget n.
  • Many NP-complete problems have an easy neighbor in P; pseudo-polynomial algorithms do not conflict with weak NP-completeness.

Next: Space Complexity, PSPACE and Savitch's Theorem