Proof of `Hitting Set Is W[2]-Complete` (3rd statement)

groundedproofs/Lax496464Proofs/WHierarchy/HittingSet/WSHSFinal.lean · lax-496464

What this proof establishes

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

Weighted monotone CNF satisfiability fpt-reduces to p−Hitting−Setp-Hitting-Set (Flum–Grohe, proof of Theorem 7.14): the clauses, read as sets of variables, are the sets. The variables are renamed by the position of their first occurrence among the literals, so the universe is the set of literal positions; the weight stays kk. Since the weight of the formula is exact and counts only its own variables, the reduction writes a fixed no-instance when kk exceeds the number of variables, and otherwise a hitting set of size at most kk pads to one of size kk inside the variables. An empty clause becomes an empty set, and the empty formula is 00-satisfiable only, both as in Hitting Set. The parameter is at most k+1k + 1, and an IMP+ program computes the reduction within 20000(∣x∣+1)320000 (|x| + 1)^3 steps.