NP-Hard Problems, in depth: hardness beyond NP, counting and games, parameterized algorithms with a tested vertex cover kernel, and exact solvers under a deadline

The definition and the direction of reductions

Formally, a problem H is NP-hard if for every L in NP there is a polynomial-time reduction from L to H. In practice you show it once: reduce one known NP-hard problem to H, and the transitivity of reductions does the rest. The direction is the classic mistake. Reducing H to SAT proves H is no harder than SAT, which is an upper bound and a useful implementation plan, but proves nothing about hardness. Reducing SAT to H proves hardness. The Karp reductions article walks through worked reductions in the correct direction.

Two flavours of reduction matter here. Karp (many-one) reductions map instances to instances and preserve yes/no answers; they are the right tool for NP-completeness. Cook (Turing) reductions may call an oracle for H many times, and they are the natural tool once H is an optimisation or counting problem, because the answer is no longer a single bit. Most statements of the form "the optimisation version is NP-hard" are Cook reductions: an algorithm that returns the optimal tour answers the decision question "is there a tour of cost at most B" with one call and one comparison.

Hardness beyond NP

Optimisation versions. The decision problem "is there a vertex cover of size at most k" is in NP, because a proposed cover is a short certificate you can check. The optimisation problem "output a minimum vertex cover" is NP-hard but not obviously in NP: to verify that a cover is minimum you would need to certify that no smaller cover exists, which is a co-NP-style statement. This is why a solver that reports "optimal" is making a stronger claim than one that reports "feasible", and why exact solvers attach a proof object, the lower bound, to their answer.

Counting. #SAT asks how many satisfying assignments a formula has. It is #P-complete, and counting is often harder than deciding: deciding whether a bipartite graph has a perfect matching takes polynomial time, but counting its perfect matchings, which equals the permanent of the biadjacency matrix, is #P-complete (Valiant, 1979). Probabilistic inference, model counting and exact reliability calculations land here, so a fast decision procedure does not imply a fast counter.

Alternation. Quantified Boolean formulas (QBF), where variables are bound by alternating "for all" and "there exists", are PSPACE-complete, as are many generalised two-player games. Adversarial planning and verification of systems against an environment often have this shape; a SAT solver alone cannot express it.

Undecidable. The halting problem is NP-hard: map a formula to a program that tries every assignment and halts if one satisfies it. It is not in NP, or in any decidable class. The lesson is that NP-hard is a lower bound only; it says your problem is at least as hard as SAT, and it can be much harder.

Parameterized complexity: hardness has a shape

Classical complexity measures cost against one number, the input size n. Parameterized complexity adds a second number k, a property of the instance such as the solution size, the treewidth of a graph, or the number of distinct job types. A problem is fixed-parameter tractable (FPT) if it can be solved in time f(k) times a polynomial in n, where f may be exponential but depends only on k. With k = 20 and n = 10 million, 2^k times n is about 10^13 elementary steps in the worst case and usually far fewer; n^k is hopeless.

Vertex cover parameterized by solution size k is the textbook FPT problem. Clique parameterized by k is the textbook counterexample: it is W[1]-hard, and the standard conjecture FPT is not equal to W[1] says no f(k) times n^c algorithm exists, so the brute-force n^k is essentially the best you get. Two problems with the same classical label, NP-complete, therefore behave completely differently once you ask which parameter is small in your data.

FPT algorithms are usually built from two tools. A kernel is a polynomial-time reduction that shrinks an instance to size bounded by a function of k alone while preserving the answer. A bounded search tree branches on a small set of choices, at least one of which must be right, and decreases k on every branch, so the tree has at most c^k leaves.

A vertex cover kernel and bounded search tree

The Buss kernel for vertex cover uses two observations. A vertex with degree greater than k must be in every cover of size at most k, because otherwise all of its more than k neighbours would have to be in the cover. And once every degree is at most k, k vertices can cover at most k squared edges, so a larger remainder is a certain no. The bounded search tree then picks any uncovered edge (u, v): one endpoint must be in the cover, so try both.

def vc_kernel(edges, k):
    """Buss kernel: (edges, k_left, forced) or None when no cover of size k exists."""
    edges = {tuple(sorted(e)) for e in edges if e[0] != e[1]}
    forced = set()
    changed = True
    while changed:
        changed = False
        deg = {}
        for u, v in edges:
            deg[u] = deg.get(u, 0) + 1
            deg[v] = deg.get(v, 0) + 1
        for x, d in deg.items():
            if d > k:                    # x is in every cover of size <= k
                forced.add(x)
                edges = {e for e in edges if x not in e}
                k -= 1
                changed = True
                break
        if k < 0:
            return None
    if len(edges) > k * k:               # max degree <= k: k vertices cover <= k*k edges
        return None
    return edges, k, forced

def vc_branch(edges, k):
    """Bounded search tree: at most 2^k leaves, O(2^k * m) time."""
    if not edges:
        return set()
    if k == 0:
        return None
    u, v = next(iter(edges))
    for x in (u, v):                     # one endpoint of (u, v) must be chosen
        rest = vc_branch({e for e in edges if x not in e}, k - 1)
        if rest is not None:
            return rest | {x}
    return None

def vc_fpt(edges, k):
    ker = vc_kernel(edges, k)
    if ker is None:
        return None
    es, k_left, forced = ker
    sol = vc_branch(es, k_left)
    return None if sol is None else sol | forced

Cross-check any such algorithm before trusting it. The version above was compared with exhaustive search on 300 random graphs of 2 to 11 vertices, for every k from 0 to n: it returned a cover exactly when k was at least the true optimum, and every returned set was a valid cover of size at most k.

Worked example: star, cycle and path

Take a graph of 39 vertices: a star whose centre 0 has 30 leaves, a 5-cycle on vertices 31 to 35, and a path 36-37-38. The optimum cover, confirmed by brute force, has size 5: the star centre, three cycle vertices (an odd cycle of length 5 needs three), and the path's middle vertex. Here is what the kernel and branching did for three budgets.

Three things are visible. The kernel deleted 30 of 37 edges in one step, and for k = 3 it answered without any search. The search runs only on the 7-edge remainder, whatever the size of the star, which is the point of a kernel: the exponential part depends on k, not n. And proving "no" cost more than finding "yes": 15 calls to exhaust the tree for k = 4 against 6 calls to find a cover for k = 5. In production that asymmetry shows up as a solver that finds a good solution quickly and then spends most of its budget proving nothing better exists.

To get the optimum rather than a yes/no answer, call vc_fpt with k = 0, 1, 2 and so on until it succeeds, or binary search on k. Stronger kernels exist: the LP relaxation of vertex cover has a half-integral optimum, and the Nemhauser-Trotter theorem turns that into a kernel with at most 2k vertices. Smarter branching, on a vertex of degree 3 or more (take it, or take all its neighbours), shrinks the base of the exponent below 2.

Exact solvers and proven bounds

When no small parameter exists, the next option is a general exact solver: mixed integer programming (MIP), SAT, or constraint programming. All three are branch-and-bound at heart. They split the search space, compute a bound for each part (an LP relaxation, a propagated domain, a learned clause), and discard parts whose bound cannot beat the best solution found so far. Seed them with a heuristic solution so pruning starts at the first node. Here is vertex cover in OR-Tools CP-SAT:

from ortools.sat.python import cp_model

def min_vertex_cover(n, edges, seconds=10.0):
    m = cp_model.CpModel()
    x = [m.NewBoolVar(f"x{v}") for v in range(n)]
    for u, v in edges:
        m.AddBoolOr([x[u], x[v]])          # every edge has a chosen endpoint
    m.Minimize(sum(x))
    s = cp_model.CpSolver()
    s.parameters.max_time_in_seconds = seconds
    status = s.Solve(m)
    if status not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        return None
    cover = [v for v in range(n) if s.Value(x[v])]
    # The gap between the objective and the proven bound is your quality guarantee.
    return cover, s.ObjectiveValue(), s.BestObjectiveBound(), status == cp_model.OPTIMAL

Return the bound as well as the solution. For example, a cover of 112 with a proven lower bound of 110 is within 2 of optimal even if the solver never proves optimality, and that statement is worth more to a stakeholder than "the solver timed out". For satisfiability-shaped problems, the SAT solving article explains what CDCL solvers do with your encoding.

Operational guidance

• Measure your instance distribution before choosing. Worst-case hardness says nothing about the instances you actually see. Collect a few hundred real instances, record n and candidate parameters (solution size, treewidth, number of distinct items), and time an exact solver on them before building anything clever.
• Always run under a deadline and keep the incumbent. Use anytime algorithms that hold a best-so-far solution, and return it with its bound when the budget expires. Never let a request thread wait on an unbounded exact search.
• Track the gap as a metric. Log objective, bound and time per solve. A creeping gap is the first sign your instances are drifting out of the easy regime.
• Use approximation when you need a guarantee and speed together. The approximation algorithms article covers ratio guarantees, and PTAS and FPTAS covers schemes that trade accuracy for time continuously.
• Pin solver versions. MIP and SAT performance varies between releases and even with the random seed; record both alongside results so regressions are diagnosable.

Failure modes

• Reduction in the wrong direction. Encoding your problem into SAT and declaring it NP-hard. That proves an upper bound only, and the problem may be in P.
• Hardness of the wrong variant. Citing the general problem when your instances are planar, bounded-degree, interval-structured or have small integer weights, where polynomial or pseudo-polynomial algorithms may exist.
• Assuming a decision oracle makes counting easy. Perfect matching is easy to decide and #P-complete to count; budget for sampling or approximate counting instead.
• Exponential blow-up hidden in the parameter. An FPT algorithm with k = 60 is as useless as brute force. Measure k on real data, not on examples.
• Reporting a timeout as optimal. A solver that hit its time limit returned a feasible answer; check the status and report the gap.

Trade-offs

What to do next

1. Write down the exact decision version of your problem and identify the NP-hard source problem; check the reduction runs from that source to your problem, not the other way.
2. Check whether your problem is an optimisation, counting or adversarial variant, since that decides whether SAT, MIP, model counting or QBF tooling is the right family.
3. Collect real instances and measure two or three candidate parameters; if one stays small, implement a kernel plus branching and cross-check it against brute force.
4. Otherwise model it in CP-SAT or a MIP solver with a time limit, and log objective, bound and status for every solve.
5. Add a fallback heuristic or approximation for when the gap stays open, and alert when the gap trend rises.