Hitting Set Is W[2]-Complete

Lax496464.WH_E2_HittingSetW2Complete · concepts/Lax496464/WH_E2_HittingSetW2Complete.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-Hitting-Set is W[2]-complete under fpt-reductions [FG06, Theorem 7.14]. It is in W[2] (WHE1HittingSetInW2WH_E1_HittingSetInW2), and it is W[2]-hard in two steps.

    1. Every Π2\Pi_2 weighted definability problem reduces to weighted monotone CNF satisfiability [FG06, Theorem 7.1]. Let φ=∀xˉ ∃yˉ ψ(X)\varphi = \forall \bar x\, \exists \bar y\, \psi(X) and let (A,k)(\mathcal A, k) be an instance. As in WHD07DefinabilityToWSatWH_D07_DefinabilityToWSat, the universe is restricted to a set UU of polynomially many elements. A witness is an increasing list t0<⋯<tk−1t_0 < \dots < t_{k-1} of codes of ss-tuples over UU. The propositional variables describe, for each of (k+1)D(k+1)^D blocks, the values of DD positions of that list, DD depending on ψ\psi 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 xˉ\bar x, one clause collects the block values under which some assignment to yˉ\bar y makes ψ\psi true. The weight is the number of blocks. This monotone formula replaces the propositional normalization of [FG06, Lemma 7.5].
    2. 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 kk satisfies the formula exactly when its true variables meet every clause.
    Concept map
    18 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_C2_HittingSet
    3import Lax496464.WH_C3_WeightedSat
    4
    5/-!
    6---
    7title: Hitting Set Is W[2]-Complete
    8type: theorem
    9---
    10pp-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
    131. **Every Π2\Pi_2 weighted definability problem reduces to weighted monotone CNF satisfiability**
    14 [FG06, Theorem 7.1]. Let φ=∀xˉ ∃yˉ ψ(X)\varphi = \forall \bar x\, \exists \bar y\, \psi(X) and let (A,k)(\mathcal A, k)
    15 be an instance. As in `WH_D07_DefinabilityToWSat`, the universe is restricted to a set UU of
    16 polynomially many elements. A witness is an increasing list t0<⋯<tk−1t_0 < \dots < t_{k-1} of codes of
    17 ss-tuples over UU. The propositional variables describe, for each of (k+1)D(k+1)^D *blocks*, the
    18 values of DD positions of that list, DD depending on ψ\psi 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 xˉ\bar x, one clause collects the block
    21 values under which some assignment to yˉ\bar y makes ψ\psi true. The weight is the number of
    22 blocks. This monotone formula replaces the propositional normalization of
    23 [FG06, Lemma 7.5].
    242. **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 kk satisfies the
    26 formula exactly when its true variables meet every clause.
    27-/
    28
    29namespace Lax496464.WH_E2_HittingSetW2Complete
    30
    31open Lax496464.WH_B2_FirstOrder Lax496464.WH_B3_LogicProblems Lax496464.WH_B4_Hierarchies
    32open 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
    35monotone CNF formulas [FG06, Theorem 7.1(1] for `t = 2`, via Lemmas 7.2 and 7.5). -/
    36axiom 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`. -/
    40axiom pWSat_monotone_le_hittingSet : pWSat {α | IsMonotone α} ≤ᶠᵖᵗ HittingSet
    41
    42/-- **`p-Hitting-Set` is W[2]-complete** [FG06, Theorem 7.14]. -/
    43axiom hittingSet_W2_complete : Complete (W 2) HittingSet
    44
    45end Lax496464.WH_E2_HittingSetW2Complete
    46
    Show ProofShow ProofShow Proof

    Discussion

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

    Loading discussion…