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.

Read the Lean proof on GitHub

Description

p−Dominating−Set≤fptp−Hitting−Setp-Dominating-Set ≤fpt p-Hitting-Set, by closed neighbourhoods. The universe is the vertex set, set vv is N[v]=v∪N(v)N[v] = {v} ∪ N(v), and the solution size is unchanged: a set of kk vertices dominates the graph exactly when it meets every closed neighbourhood. Each set is written sorted and without repetitions by testing the candidates 0,…,n−10, …, n-1 in order against the adjacency block of vv, so the order and repetitions of the block do not matter. The parameter is unchanged, and an IMP+ program computes the reduction within 20000(∣x∣+1)320000 (|x| + 1)^3 steps.