Dominating Set Is W[2]-Complete
Lax496464.WH_E3_DominatingSet · concepts/Lax496464/WH_E3_DominatingSet.lean · lax-496464
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
-Dominating-Set is W[2]-complete under fpt-reductions [FG06, Corollary 7.15]: it is fpt-equivalent to -Hitting-Set [FG06, Example 2.7], which is W[2]-complete ().
- Dominating Set Hitting Set. The universe is the vertex set, and the hyperedges are the closed neighbourhoods : a set dominates the graph exactly when it meets every .
- Hitting Set 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 elements dominates the graph; conversely, a dominating set of vertices yields a hitting set of 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 larger than the universe are mapped to a fixed no-instance.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax496464.WH_B4_Hierarchies |
| 2 | import Lax496464.WH_C1_GraphProblems |
| 3 | import Lax496464.WH_C2_HittingSet |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Dominating Set Is W[2]-Complete |
| 8 | type: theorem |
| 9 | --- |
| 10 | -Dominating-Set is W[2]-complete under fpt-reductions [FG06, Corollary 7.15]: it is |
| 11 | fpt-equivalent to -Hitting-Set [FG06, Example 2.7], which is W[2]-complete |
| 12 | (`WH_E2_HittingSetW2Complete`). |
| 13 | |
| 14 | * **Dominating Set Hitting Set.** The universe is the vertex set, and the hyperedges are the |
| 15 | closed neighbourhoods : a set dominates the graph exactly when it meets every . |
| 16 | * **Hitting Set 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 elements dominates the graph; conversely, a dominating set of vertices yields a |
| 19 | hitting set of 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 larger than the universe are mapped to a fixed no-instance. |
| 22 | -/ |
| 23 | |
| 24 | namespace Lax496464.WH_E3_DominatingSet |
| 25 | |
| 26 | open Lax496464.WH_B4_Hierarchies Lax496464.WH_A2_FptReductions |
| 27 | open Lax496464.WH_C1_GraphProblems Lax496464.WH_C2_HittingSet |
| 28 | |
| 29 | /-- The parameter of `p-Dominating-Set` is computable in polynomial time. -/ |
| 30 | axiom dominatingSet_isParameterized : IsParameterized DominatingSet |
| 31 | |
| 32 | /-- **`p-Dominating-Set ≤fpt p-Hitting-Set`**, by closed neighbourhoods. -/ |
| 33 | axiom dominatingSet_le_hittingSet : DominatingSet ≤ᶠᵖᵗ HittingSet |
| 34 | |
| 35 | /-- **`p-Hitting-Set ≤fpt p-Dominating-Set`** [FG06, Example 2.7]. -/ |
| 36 | axiom hittingSet_le_dominatingSet : HittingSet ≤ᶠᵖᵗ DominatingSet |
| 37 | |
| 38 | /-- **`p-Dominating-Set` is W[2]-complete** [FG06, Corollary 7.15]. -/ |
| 39 | axiom dominatingSet_W2_complete : Complete (W 2) DominatingSet |
| 40 | |
| 41 | end Lax496464.WH_E3_DominatingSet |
| 42 |
Used by
none
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments