Key NP-Complete Problems

Why This Matters

In combinatorial optimization, you're constantly bumping up against problems that seem simple to state but are maddeningly difficult to solve efficiently. NP-Complete problems represent the heart of this challenge—they're the problems where no one has found a polynomial-time algorithm, yet if someone hands you a solution, you can verify it quickly. Understanding these problems isn't just theoretical: they appear everywhere from logistics and scheduling to network design and cryptography, and the techniques you learn to handle them form the backbone of algorithm design.

Here's what you're really being tested on: reduction relationships (how one problem transforms into another), problem structure (what makes graph problems different from subset problems), and approximation strategies (what to do when exact solutions are intractable). Don't just memorize problem definitions—know which problems reduce to which, what real-world scenarios each models, and why certain problems cluster together conceptually.

---

The Foundation: Satisfiability Problems

Every NP-Complete problem traces back to satisfiability. If you can solve SAT efficiently, you can solve them all—that's the power of Cook's theorem and polynomial-time reductions.

Boolean Satisfiability Problem (SAT)

• First proven NP-Complete (Cook-Levin theorem, 1971)—this is the foundational result that launched computational complexity theory
• Decision problem: given a Boolean formula, determine if any variable assignment makes it evaluate to true
• Reduction hub—SAT transforms into virtually every other NP-Complete problem, making it the standard starting point for NP-Completeness proofs

Subset Sum Problem

• Target-finding problem: determine if any subset of integers sums exactly to a given value $T$
• Weakly NP-Complete—solvable in pseudo-polynomial time via dynamic programming when numbers are bounded
• Cryptographic applications—forms the basis of certain public-key cryptosystems and appears in financial reconciliation problems

---

Graph Traversal and Path Problems

These problems ask about visiting vertices or finding routes through graphs. The constraint is typically visiting nodes exactly once or finding optimal orderings—small changes in problem definition dramatically affect complexity.

Traveling Salesman Problem (TSP)

• Optimization goal: find the shortest route visiting all cities exactly once and returning to the start
• Metric vs. general TSP—the metric version (where distances satisfy the triangle inequality) admits a 2-approximation, while general TSP has no constant-factor approximation unless $P = NP$
• Ubiquitous applications—logistics, circuit board drilling, DNA sequencing, and anywhere route optimization matters

Hamiltonian Cycle Problem

• Existence question: does a cycle visiting every vertex exactly once exist in the graph?
• Decision version of TSP—TSP asks for the shortest Hamiltonian cycle; this just asks if any exists
• No known approximation—unlike TSP, there's no natural optimization version with good approximation guarantees

---

Graph Structure Problems

These problems focus on properties of vertex and edge arrangements—finding subgraphs, covers, or partitions with specific characteristics.

Graph Coloring Problem

• Chromatic number: assign colors to vertices so no adjacent vertices share a color, minimizing total colors used
• NP-Complete for $k \geq 3$ colors—determining if a graph is 2-colorable (bipartite) is polynomial, but 3-colorability jumps to NP-Complete
• Scheduling applications—exam scheduling, register allocation in compilers, and frequency assignment all reduce to graph coloring

Vertex Cover Problem

• Minimum covering set: find the smallest set of vertices such that every edge touches at least one selected vertex
• 2-approximation exists—a simple greedy algorithm guarantees a solution at most twice optimal, making this one of the "nicer" NP-Complete problems
• Dual relationship with Independent Set—a vertex cover's complement is an independent set, connecting these problems directly

Clique Problem

• Complete subgraph detection: determine if a graph contains a clique (fully connected subgraph) of size $k$
• Social network analysis—finding tightly-knit communities, protein interaction clusters, and fraud rings
• Complement relationship—finding a clique in graph $G$ equals finding an independent set in $\bar{G}$ (the complement graph)

---

Selection and Covering Problems

These problems involve choosing subsets to satisfy constraints—either selecting items under capacity limits or covering elements with minimum redundancy.

Knapsack Problem (0/1)

• Constrained optimization: select items with weights $w_i$ and values $v_i$ to maximize total value without exceeding capacity $W$
• 0/1 version is NP-Complete—items are indivisible; the fractional version is solvable greedily in polynomial time
• Dynamic programming solution runs in $O(nW)$—pseudo-polynomial, efficient when $W$ is small relative to input size

Set Cover Problem

• Minimum collection: choose the fewest subsets from a collection to cover all elements in a universe $U$
• Greedy approximation achieves $O(\ln n)$ factor—provably the best possible unless $P = NP$
• Applications span domains—sensor placement, test case selection, and facility location all model as Set Cover

---

Graph Partitioning Problems

These problems ask about dividing vertices into groups to optimize some edge-based objective.

Maximum Cut Problem

• Partition objective: divide vertices into two sets to maximize edges crossing between them
• 0.878-approximation via semidefinite programming (Goemans-Williamson algorithm)—a landmark result in approximation algorithms
• Physics connections—equivalent to finding ground states in certain spin glass models; appears in VLSI design and clustering

---

Quick Reference Table

---

Self-Check Questions

1. Which two problems are connected through graph complements? Explain how solving Clique in $G$ relates to solving Independent Set in $\bar{G}$.

2. Compare TSP and Hamiltonian Cycle: What's the key difference between them, and why does TSP admit approximation algorithms while Hamiltonian Cycle doesn't naturally?

3. Why is 3-colorability NP-Complete but 2-colorability polynomial? What structural property makes bipartite testing easy?

4. Identify two problems that are "weakly NP-Complete" and explain what pseudo-polynomial time means for their practical solvability.

5. FRQ-style: You need to prove a new problem $X$ is NP-Complete. Describe the two-step process, and explain why SAT is typically the starting point for reduction chains.