Hitting Set Is W[2]-Complete
Lax496464.WH_E2_HittingSetW2Complete · concepts/Lax496464/WH_E2_HittingSetW2Complete.lean · lax-496464
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
-Hitting-Set is W[2]-complete under fpt-reductions [FG06, Theorem 7.14]. It is in W[2] (), and it is W[2]-hard in two steps.
- Every weighted definability problem reduces to weighted monotone CNF satisfiability [FG06, Theorem 7.1]. Let and let be an instance. As in , the universe is restricted to a set of polynomially many elements. A witness is an increasing list of codes of -tuples over . The propositional variables describe, for each of blocks, the values of positions of that list, depending on only. Monotone clauses force exactly one value per block and the consistency of any two blocks, so that the true variables describe a single list; and for every assignment to , one clause collects the block values under which some assignment to makes true. The weight is the number of blocks. This monotone formula replaces the propositional normalization of [FG06, Lemma 7.5].
- Weighted monotone CNF satisfiability reduces to Hitting Set [FG06, Theorem 7.14]: the hyperedges are the clauses, read as sets of variables; an assignment of weight satisfies the formula exactly when its true variables meet every clause.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax496464.WH_B4_Hierarchies |
| 2 | import Lax496464.WH_C2_HittingSet |
| 3 | import Lax496464.WH_C3_WeightedSat |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Hitting Set Is W[2]-Complete |
| 8 | type: theorem |
| 9 | --- |
| 10 | -Hitting-Set is W[2]-complete under fpt-reductions [FG06, Theorem 7.14]. It is in W[2] |
| 11 | (`WH_E1_HittingSetInW2`), and it is W[2]-hard in two steps. |
| 12 | |
| 13 | 1. **Every weighted definability problem reduces to weighted monotone CNF satisfiability** |
| 14 | [FG06, Theorem 7.1]. Let and let |
| 15 | be an instance. As in `WH_D07_DefinabilityToWSat`, the universe is restricted to a set of |
| 16 | polynomially many elements. A witness is an increasing list of codes of |
| 17 | -tuples over . The propositional variables describe, for each of *blocks*, the |
| 18 | values of positions of that list, depending on only. Monotone clauses force |
| 19 | exactly one value per block and the consistency of any two blocks, so that the true variables |
| 20 | describe a single list; and for every assignment to , one clause collects the block |
| 21 | values under which some assignment to makes true. The weight is the number of |
| 22 | blocks. This monotone formula replaces the propositional normalization of |
| 23 | [FG06, Lemma 7.5]. |
| 24 | 2. **Weighted monotone CNF satisfiability reduces to Hitting Set** [FG06, Theorem 7.14]: the |
| 25 | hyperedges are the clauses, read as sets of variables; an assignment of weight satisfies the |
| 26 | formula exactly when its true variables meet every clause. |
| 27 | -/ |
| 28 | |
| 29 | namespace Lax496464.WH_E2_HittingSetW2Complete |
| 30 | |
| 31 | open Lax496464.WH_B2_FirstOrder Lax496464.WH_B3_LogicProblems Lax496464.WH_B4_Hierarchies |
| 32 | open Lax496464.WH_A2_FptReductions Lax496464.WH_C2_HittingSet Lax496464.WH_C3_WeightedSat |
| 33 | |
| 34 | /-- **Step 1:** weighted definability of a `Π_2`-sentence fpt-reduces to weighted satisfiability of |
| 35 | monotone CNF formulas [FG06, Theorem 7.1(1] for `t = 2`, via Lemmas 7.2 and 7.5). -/ |
| 36 | axiom pWD_le_pWSat_monotone {φ : Formula} (s : ℕ) (hφ : IsPi 2 φ) (hs : IsSentence φ) : |
| 37 | pWD φ s ≤ᶠᵖᵗ pWSat {α | IsMonotone α} |
| 38 | |
| 39 | /-- **Step 2:** weighted monotone CNF satisfiability fpt-reduces to `p-Hitting-Set`. -/ |
| 40 | axiom pWSat_monotone_le_hittingSet : pWSat {α | IsMonotone α} ≤ᶠᵖᵗ HittingSet |
| 41 | |
| 42 | /-- **`p-Hitting-Set` is W[2]-complete** [FG06, Theorem 7.14]. -/ |
| 43 | axiom hittingSet_W2_complete : Complete (W 2) HittingSet |
| 44 | |
| 45 | end Lax496464.WH_E2_HittingSetW2Complete |
| 46 |
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