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.
Description
Weighted monotone CNF satisfiability fpt-reduces to (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 . Since the weight of the formula is exact and counts only its own variables, the reduction writes a fixed no-instance when exceeds the number of variables, and otherwise a hitting set of size at most pads to one of size inside the variables. An empty clause becomes an empty set, and the empty formula is -satisfiable only, both as in Hitting Set. The parameter is at most , and an IMP+ program computes the reduction within steps.