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.

Read the Lean proof on GitHub

Description

p−Hitting−Set≤fptp−Dominating−Setp-Hitting-Set ≤fpt p-Dominating-Set (Flum–Grohe, Example 2.7). On the word of (P,k)(P, k) with k≤nk ≤ n and no empty set, the reduction writes the graph of the compressed instance — its elements (the first occurrences of the members and minkmmin k m spare elements) form a clique, and each set is a vertex joined to its elements — with parameter minkmmin k m; otherwise a fixed no-instance. The new parameter is at most k+1k + 1, and an IMP+ program computes the reduction within 100000(∣x∣+1)3100000 (|x| + 1)^3 steps.