Dominating Set Is W[2]-Complete

Lax496464.WH_E3_DominatingSet · concepts/Lax496464/WH_E3_DominatingSet.lean · lax-496464

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Theorem

    pp-Dominating-Set is W[2]-complete under fpt-reductions [FG06, Corollary 7.15]: it is fpt-equivalent to pp-Hitting-Set [FG06, Example 2.7], which is W[2]-complete (WHE2HittingSetW2CompleteWH_E2_HittingSetW2Complete).

    • Dominating Set ≤\le Hitting Set. The universe is the vertex set, and the hyperedges are the closed neighbourhoods N[v]N[v]: a set dominates the graph exactly when it meets every N[v]N[v].
    • Hitting Set ≤\le Dominating Set. The graph has a vertex for every element and every hyperedge; the elements form a clique, and an element is joined to the hyperedges containing it. A hitting set of kk elements dominates the graph; conversely, a dominating set of kk vertices yields a hitting set of kk elements by replacing each hyperedge-vertex by an element of that hyperedge. The universe is first restricted to the elements occurring in the sets; instances with an empty hyperedge or with kk larger than the universe are mapped to a fixed no-instance.
    Concept map
    19 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    Lean source view on GitHub

    1import Lax496464.WH_B4_Hierarchies
    2import Lax496464.WH_C1_GraphProblems
    3import Lax496464.WH_C2_HittingSet
    4
    5/-!
    6---
    7title: Dominating Set Is W[2]-Complete
    8type: theorem
    9---
    10pp-Dominating-Set is W[2]-complete under fpt-reductions [FG06, Corollary 7.15]: it is
    11fpt-equivalent to pp-Hitting-Set [FG06, Example 2.7], which is W[2]-complete
    12(`WH_E2_HittingSetW2Complete`).
    13
    14* **Dominating Set ≤\le Hitting Set.** The universe is the vertex set, and the hyperedges are the
    15 closed neighbourhoods N[v]N[v]: a set dominates the graph exactly when it meets every N[v]N[v].
    16* **Hitting Set ≤\le Dominating Set.** The graph has a vertex for every element and every hyperedge;
    17 the elements form a clique, and an element is joined to the hyperedges containing it. A hitting
    18 set of kk elements dominates the graph; conversely, a dominating set of kk vertices yields a
    19 hitting set of kk elements by replacing each hyperedge-vertex by an element of that hyperedge.
    20 The universe is first restricted to the elements occurring in the sets; instances with an empty
    21 hyperedge or with kk larger than the universe are mapped to a fixed no-instance.
    22-/
    23
    24namespace Lax496464.WH_E3_DominatingSet
    25
    26open Lax496464.WH_B4_Hierarchies Lax496464.WH_A2_FptReductions
    27open Lax496464.WH_C1_GraphProblems Lax496464.WH_C2_HittingSet
    28
    29/-- The parameter of `p-Dominating-Set` is computable in polynomial time. -/
    30axiom dominatingSet_isParameterized : IsParameterized DominatingSet
    31
    32/-- **`p-Dominating-Set ≤fpt p-Hitting-Set`**, by closed neighbourhoods. -/
    33axiom dominatingSet_le_hittingSet : DominatingSet ≤ᶠᵖᵗ HittingSet
    34
    35/-- **`p-Hitting-Set ≤fpt p-Dominating-Set`** [FG06, Example 2.7]. -/
    36axiom hittingSet_le_dominatingSet : HittingSet ≤ᶠᵖᵗ DominatingSet
    37
    38/-- **`p-Dominating-Set` is W[2]-complete** [FG06, Corollary 7.15]. -/
    39axiom dominatingSet_W2_complete : Complete (W 2) DominatingSet
    40
    41end Lax496464.WH_E3_DominatingSet
    42
    Show ProofShow ProofShow ProofShow Proof

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…