5.3Easy versus hard variants
The idea
Many problems have an easy and a hard version that differ by one small change.
Think of it like this: Finding a short route is easy; finding a route that visits every town exactly once is a nightmare.
Why it exists
Exam options mix these pairs to see whether you know which side is which.
How it works
- 2-SAT is in P; 3-SAT is NP-complete.
- Euler circuit is in P; Hamiltonian cycle is NP-complete.
- Shortest simple path is in P; longest simple path is NP-hard.
- MST is in P; TSP is NP-hard; fractional knapsack is in P, 0/1 knapsack NP-complete.
Worked example: Which is NP-complete?
Of {2-SAT, MST, Euler circuit, Hamiltonian cycle}, only Hamiltonian cycle is.
Now play with it
- →Cover the right column and try to name the hard twin of each easy problem.
- →Remember: 0/1 knapsack has an O(nW) DP but is still NP-complete.
| In P (easy) | NP-complete (hard) |
|---|---|
| 2-SAT | 3-SAT |
| 2-colourability (bipartite test) | 3-colourability |
| Euler circuit | Hamiltonian cycle |
| Shortest simple path | Longest simple path |
| Minimum spanning tree | Travelling salesman (decision) |
| Bipartite matching | 3-dimensional matching |
| Fractional knapsack (greedy) | 0/1 knapsack (NP-complete, but O(nW) DP) |
| Vertex cover on trees | Vertex cover on general graphs |
Pairs that look alike but sit on opposite sides: a favourite way to build "which is NP-complete?" questions.
Check yourself
Which of these is solvable in polynomial time?
Exam notes (the dense version)
Small changes flip the class: 2-SAT is in P, 3-SAT is NP-complete; 2-colouring is in P, 3-colouring is NP-complete; shortest path is in P, longest simple path is NP-hard; MST is in P, TSP is NP-hard; Eulerian circuit is in P, Hamiltonian cycle is NP-complete; matching is in P, 3-dimensional matching is NP-complete. Knapsack is NP-complete but has a pseudo-polynomial DP.