Proof of `Dominating Set Is W[2]-Complete` (2nd statement)
groundedproofs/Lax496464Proofs/WHierarchy/HittingSet/DSHSFinal.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
, by closed neighbourhoods. The universe is the vertex set, set is , and the solution size is unchanged: a set of vertices dominates the graph exactly when it meets every closed neighbourhood. Each set is written sorted and without repetitions by testing the candidates in order against the adjacency block of , so the order and repetitions of the block do not matter. The parameter is unchanged, and an IMP+ program computes the reduction within steps.