Skip to content
Tutorials Center
My learning

Topics

Lesson 50 of 59 ยท Complexity

Coping with NP-Hard Problems

What to do when a problem is NP-hard: approximation algorithms, heuristics, special cases, parameterized algorithms and randomization, with Python vertex cover and TSP examples.

Suppose your boss hands you a scheduling problem and you recognize it as NP-complete. Does this mean you give up? Not at all. NP-completeness is a statement about the worst case and about exact optimal answers. Real applications routinely solve huge NP-hard instances. They simply give up one of the three things a perfect algorithm would need: speed, optimality, or generality.

This final lesson of the chapter surveys the practical toolbox and, with two programs, shows how much you can get without finding the exact optimum.

The toolbox

flowchart TD
    H["NP-hard problem"] --> A["Approximation<br/>provably near-optimal, fast"]
    H --> HE["Heuristics<br/>good in practice, no guarantee"]
    H --> S["Special cases<br/>restrict the input"]
    H --> F["Parameterized<br/>exponential only in a small k"]
    H --> R["Randomization<br/>probably correct or probably good"]
    H --> E["Exact but clever<br/>branch and bound, SAT solvers"]

Six ways to live with an NP-hard problem. Each gives up something different.

  • Approximation: run in polynomial time, return a solution at most a factor ฯ worse than the optimum (the approximation ratio), and prove it.
  • Heuristics and local search: greedy rules, hill climbing, simulated annealing, genetic algorithms. Often excellent, rarely provable.
  • Special cases: many NP-hard graph problems become easy on trees, bipartite graphs or planar graphs; scheduling can be easy when all jobs have equal length.
  • Parameterized algorithms: if some parameter k is small, an O(2^k ยท n) algorithm is fine even if n is huge (this is the class FPT, fixed-parameter tractable).
  • Randomized algorithms: sample solutions and keep the best; random restarts escape bad local optima.
  • Exact solvers with pruning: branch and bound, integer linear programming, and modern SAT solvers (CDCL) handle millions of variables on structured industrial instances although the worst case is still exponential.

A guaranteed approximation: vertex cover

Recall VERTEX-COVER: choose as few vertices as possible so that every edge has an endpoint chosen. Finding the minimum cover is NP-hard, but there is a charmingly simple 2-approximation:

TEXT
APPROX-VC(G):
    C = empty set
    while G has an uncovered edge (u, v):
        add both u and v to C
        remove every edge touching u or v
    return C

Why is it within a factor 2? The edges chosen form a matching (no two share an endpoint, because both endpoints were removed). Any cover, including the optimal one, must contain at least one endpoint of each matching edge, so |OPT| โ‰ฅ number of chosen edges. Our cover has exactly twice that many vertices: |C| = 2 ยท (chosen edges) โ‰ค 2 ยท |OPT|.

Python 2-approximation for vertex cover versus the optimum

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.

The ratio never exceeds 2, as promised. In practice it is often far better, but the proof guarantees it even for adversarial graphs.

When approximation itself is impossible

Not every problem can be approximated. The PCP theorem implies that some problems have no good approximation unless P = NP. General TSP (with arbitrary distances) cannot be approximated within any constant factor in polynomial time unless P = NP: otherwise you could use that algorithm to solve Hamiltonian cycle with the weight-1-or-huge trick from the last lesson. If the distances obey the triangle inequality (a metric), however, simple algorithms get within factor 2 (double tree) or 1.5 (Christofides). The picture varies a lot from problem to problem:

Problem Best polynomial-time guarantee (unless P = NP)
Vertex cover factor 2; not better than about 1.36
Metric TSP factor 1.5 (Christofides)
General TSP no constant factor at all
Max-3SAT factor 7/8 by a random assignment; 7/8 is optimal
Knapsack FPTAS: factor (1 + ฮต) for any ฮต
Clique essentially no good approximation

An FPTAS (fully polynomial-time approximation scheme) is the gold standard: for every ฮต > 0 it gets within 1 + ฮต of the optimum in time polynomial in both n and 1/ฮต.

A practical heuristic: nearest neighbor plus 2-opt for TSP

For tours through random points we can use two cheap steps. Nearest neighbor starts at a city and always travels to the closest unvisited city. 2-opt then repeatedly looks for two edges whose removal and reconnection (reversing a segment) shortens the tour, and stops when no such move helps. There is no worst-case guarantee, but the result is usually within a few percent of optimal.

Python TSP heuristics compared with the optimal tour

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.

Exhaustive search must look at (n-1)! tours; at n = 9 that is only 40,320, but at n = 25 it is more than 10^23. The heuristics scale to hundreds of thousands of cities, and specialized solvers have solved real instances with tens of thousands of cities to proven optimality.

Parameterized thinking

Suppose you only need to know whether a vertex cover of size at most k exists, and k is small (say 20) even though the graph has a million vertices. Pick any edge (u, v): one of its endpoints must be in the cover. Branch on the two choices and recurse with k - 1. The search tree has at most 2^k leaves, so the running time is O(2^k ยท (n + m)). The exponential part depends only on k, not on the graph size: the problem is fixed-parameter tractable. Choosing the parameter well is the art.

Choosing a strategy

  1. Understand the instances. Are they small? Structured? Is k small? Special structure beats general algorithms.
  2. Do you need the optimum? If 95% of optimal is acceptable, use an approximation algorithm or local search.
  3. Try a solver first. Modern ILP and SAT solvers are astonishingly strong; encode the problem and test before writing custom code.
  4. Measure. Worst-case theory says nothing about your data. Benchmark on realistic inputs.

Complexity theory still helps: an NP-completeness proof tells you not to waste months looking for an exact polynomial algorithm and points you toward the approaches above.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why is the simple matching-based vertex cover algorithm a 2-approximation?

    The chosen edges form a matching, so the optimum has at least that many vertices, while the algorithm uses exactly twice as many.
  2. 2. What is an FPTAS?

    Fully polynomial-time approximation schemes trade accuracy for time smoothly. Knapsack has one.
  3. 3. Why can general (non-metric) TSP not be approximated within a constant factor unless P = NP?

    Give non-edges a huge weight; a constant-factor approximation would then tell apart a tour of weight n from a much heavier one, deciding Hamiltonian cycle.
  4. 4. A problem is fixed-parameter tractable with parameter k if it can be solved in time

    The exponential blow-up is confined to the function f(k) of the parameter; the dependence on the input size n is polynomial.

Summary

  • NP-hardness is a worst-case statement about exact solutions; there are many practical ways around it.
  • Approximation algorithms give provable guarantees (vertex cover: 2, metric TSP: 1.5); some problems cannot be approximated at all unless P = NP.
  • Heuristics such as nearest neighbor with 2-opt work very well without guarantees.
  • Parameterized algorithms confine the exponential cost to a small parameter k.
  • Check special cases, try SAT/ILP solvers, and benchmark on your real data.

Next: Project: A DFA Simulator and Minimizer