Proof of `Dominating Set Is W[2]-Complete` (4th statement)
groundedproofs/Lax496464Proofs/WHierarchy/HittingSet/DSFinal.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
(Flum–Grohe, Example 2.7). On the word of with and no empty set, the reduction writes the graph of the compressed instance — its elements (the first occurrences of the members and spare elements) form a clique, and each set is a vertex joined to its elements — with parameter ; otherwise a fixed no-instance. The new parameter is at most , and an IMP+ program computes the reduction within steps.