NP-Complete Problems

NP-Complete Problems

Classic NP-Complete Problems

1. Traveling Salesman Problem (TSP)

Given cities and distances, find shortest tour visiting each city once.

2. Hamiltonian Cycle

Does graph contain cycle visiting each vertex exactly once?

3. Vertex Cover

Find minimum vertices covering all edges.

4. Clique

Find maximum complete subgraph.

5. Independent Set

Find maximum vertices with no edges between them.

6. Set Cover

Given sets, find minimum sets covering universe.

7. Subset Sum

Given numbers, does subset sum to target?

8. Partition

Can numbers be partitioned into equal-sum subsets?

9. Knapsack (Decision)

Can items fit in knapsack with value ≥ k?

10. Graph Coloring

Can graph be colored with k colors?

Reduction Chain

SAT → 3-SAT → Independent Set → Vertex Cover → Clique → ...

Practice Problems

1. Prove problem is NP-complete
2. Find reduction between problems
3. Identify polynomial-time variants