Exercise 7
NP-Complexity Classification
Exam Format & Expectations
NP-Complexity classification questions ask you to:
- Classify problems - Is it in P, NP-complete, or unknown?
- Justify your answer - Give algorithm or cite known result
- Recognize variations - How do constraints affect complexity?
Good news: This is often the easiest exercise! You just need to recognize problems and know their complexity.
Quick Classification Guide
Problems in P
- • Shortest Path (Dijkstra, Bellman-Ford)
- • Maximum Flow (Edmonds-Karp)
- • Bipartite Matching (Hungarian)
- • Minimum Spanning Tree (Kruskal, Prim)
- • 2-SAT (SCC algorithm)
- • Linear Programming (ellipsoid/interior point)
NP-Complete Problems
- • 3-SAT (but not 2-SAT!)
- • Traveling Salesman (TSP)
- • Knapsack (0/1 version)
- • Graph Coloring (k ≥ 3)
- • Hamiltonian Path/Cycle
- • Set Cover
- • Subset Sum
- • Clique, Independent Set, Vertex Cover
Past Exam Example: Problem Classification (2024)
Classify each problem as "in P" or "NP-complete":
Shortest path from s to t in a weighted graph
In P
Algorithm: Dijkstra's algorithm runs in O(V log V + E) with Fibonacci heaps.
For negative weights: Bellman-Ford in O(VE).
Does graph G have a Hamiltonian cycle?
✗NP-complete
Known NP-complete problem. Part of Karp's 21 NP-complete problems.
No polynomial algorithm known.
Maximum matching in a bipartite graph
In P
Algorithm: Hungarian algorithm O(V³) or reduction to max flow.
Also: Hopcroft-Karp in O(E√V).
Can graph G be colored with 3 colors?
✗NP-complete
3-COLORING is NP-complete (can reduce from 3-SAT).
Note: 2-coloring is in P (check bipartiteness with BFS).
Minimum spanning tree of a weighted graph
In P
Algorithms: Kruskal's O(E log E) or Prim's O(E + V log V).
Important Variations to Remember
SAT Variants
2-SAT: In P ✓
Solve with SCC algorithm in O(n+m)
3-SAT: NP-complete ✗
The canonical NP-complete problem
Graph Coloring
2-coloring: In P ✓
Check if bipartite with BFS/DFS
k-coloring (k ≥ 3): NP-complete ✗
Even 3-coloring is NP-complete
Path Problems
Shortest Path: In P ✓
Dijkstra, Bellman-Ford, Floyd-Warshall
Longest Path: NP-complete ✗
Reduces from Hamiltonian Path
Tips for Maximum Points
For "In P" problems:
- 1. Name the specific algorithm
- 2. State its time complexity
- 3. Mention if there are multiple algorithms
- 4. Be specific (e.g., "Dijkstra with Fibonacci heaps")
For "NP-complete" problems:
- 1. State it's a known NP-complete problem
- 2. Mention a possible reduction if you know one
- 3. Don't confuse with similar P problems
- 4. Note any special cases that ARE in P
Exam Strategy
This is often a "free points" question if you've memorized the classifications. Spend 5-10 minutes max here and save time for harder problems.
Common Mistakes to Avoid
- Confusing 2-SAT with 3-SAT: 2-SAT is in P, 3-SAT is NP-complete!
- Forgetting special cases: 2-coloring is easy, 3-coloring is hard.
- Wrong algorithm names: It's "Dijkstra" not "Djikstra" or "Dijsktra".
- Vague justifications: Don't just say "use dynamic programming" - be specific!