[Model] MinimumHittingSet

[isPANN]

Motivation

HITTING SET (P135) from Garey & Johnson, A3 SP8. A classical NP-complete problem useful for reductions. It is the dual of SET COVER: while Set Cover asks which sets to pick to cover all universe elements, Hitting Set asks which universe elements to pick to "hit" all sets. Every instance of VERTEX COVER reduces to HITTING SET by encoding each edge as a 2-element subset.

Although MinimumSetCovering already exists in the codebase (the LP dual), MinimumHittingSet has genuinely different variable semantics: variables represent universe elements (which to select) rather than sets (which to pick). This means dims(), evaluate(), and the schema are structurally different — analogous to how MinimumVertexCover and MinimumSetCovering coexist despite VC being a special case of SC. Having both models enables natural reduction chains (e.g., MinimumVertexCover → MinimumHittingSet) and captures the element-selection perspective that downstream reductions to database problems (#460, #462, #467) require.

Definition

Name: MinimumHittingSet
Canonical name: Minimum Hitting Set (also: Minimum Transversal)
Reference: Garey & Johnson, Computers and Intractability, A3 SP8

Mathematical definition:

INSTANCE: Collection C of subsets of a finite set S.
OBJECTIVE: Find a subset S' ⊆ S of minimum cardinality such that S' contains at least one element from each subset in C.

The original GJ formulation is a decision problem with budget K; here we use the optimization variant (minimize |S'|) per project conventions.

Variables

• Count: |S| (one binary variable per universe element)
• Per-variable domain: binary {0, 1} — whether element s ∈ S is included in the hitting set S'
• Meaning: variable x_i = 1 if element i is selected into the hitting set; the configuration (x_0, ..., x_{|S|-1}) encodes a candidate subset S' ⊆ S. The assignment is valid if for every subset c ∈ C, at least one element of c has x_i = 1. The objective is to minimize |S'| = ∑ x_i.

Schema (data type)

Type name: MinimumHittingSet
Variants: none (no graph or weight type parameter needed; the collection is stored directly)

Field	Type	Description
universe_size	usize	Number of elements in S (elements are indexed 0..universe_size)
sets	Vec<Vec<usize>>	The collection C; each inner Vec is a subset of element indices

Complexity

• Decision complexity: NP-complete (Karp, 1972; transformation from VERTEX COVER).
• Best known exact algorithm: Brute-force enumeration of all 2^|S| subsets of S in O(2^|S| · |C|) time. No better general exact algorithm is known since Hitting Set is W[2]-hard parameterized by solution size.
• declare_variants! complexity string: "2^universe_size"
• Parameterized: W[2]-complete parameterized by solution size k, meaning no FPT algorithm parameterized by k is expected under standard complexity assumptions. FPT algorithms exist for d-bounded instances (each subset has size ≤ d): for 3-Hitting Set, the best known bound is O*(2.0409^k) (Tsur, 2025), improving earlier results of O*(2.270^k) (Niedermeier & Rossmanith, 2003).
• References:
  • [Karp, 1972] R. M. Karp, "Reducibility Among Combinatorial Problems", Complexity of Computer Computations, pp. 85–103. Original NP-completeness proof.
  • [Niedermeier & Rossmanith, 2003] R. Niedermeier, P. Rossmanith, "An efficient fixed-parameter algorithm for 3-Hitting Set", Journal of Discrete Algorithms 1(1), pp. 89–102. https://doi.org/10.1016/S1570-8667(03)00009-1
  • [Tsur, 2025] D. Tsur, "Faster parameterized algorithm for 3-Hitting Set", arXiv:2501.06452. Current best FPT bound for 3-Hitting Set.

Specialization

• This is a generalization of: VERTEX COVER (special case where every subset has exactly 2 elements, corresponding to edges)
• Known special cases: VERTEX COVER (|c| = 2 for all c ∈ C), 3-Hitting Set (|c| ≤ 3 for all c ∈ C)
• Restriction: VERTEX COVER is obtained by restricting C to 2-element subsets (edges of a graph)

Extra Remark

Full book text:

INSTANCE: Collection C of subsets of a finite set S, positive integer K ≤ |S|.
QUESTION: Is there a subset S' ⊆ S with |S'| ≤ K such that S' contains at least one element from each subset in C?
Reference: [Karp, 1972]. Transformation from VERTEX COVER.
Comment: Remains NP-complete even if |c| ≤ 2 for all c ∈ C.

How to solve

• It can be solved by (existing) bruteforce. Enumerate all 2^|S| subsets of S; for each candidate S', check if it hits every subset in C and count |S'|; return the smallest valid S'.
• It can be solved by reducing to integer programming. Introduce binary variable x_i for each element; minimize ∑x_i subject to ∑_{i∈c} x_i ≥ 1 for all c ∈ C.
• Other: (none identified)

Example Instance

Universe S = {0, 1, 2, 3, 4, 5} (6 elements)
Collection C (7 subsets):

• c_0 = {0, 1, 2}
• c_1 = {0, 3, 4}
• c_2 = {1, 3, 5}
• c_3 = {2, 4, 5}
• c_4 = {0, 1, 5}
• c_5 = {2, 3}
• c_6 = {1, 4}

Brute-force complexity: 2^6 = 64 candidate subsets to enumerate.

Greedy trap: Greedily picking the element appearing most often might pick element 1 (appears in c_0, c_2, c_4, c_6 — 4 subsets), but this alone leaves c_1, c_3, c_5 uncovered and we still need 2 more elements. A better choice requires looking at coverage interaction.

Optimal hitting set: S' = {1, 3, 4} (size 3):

• c_0 = {0,1,2}: 1 ∈ S' ✓
• c_1 = {0,3,4}: 3,4 ∈ S' ✓
• c_2 = {1,3,5}: 1,3 ∈ S' ✓
• c_3 = {2,4,5}: 4 ∈ S' ✓
• c_4 = {0,1,5}: 1 ∈ S' ✓
• c_5 = {2,3}: 3 ∈ S' ✓
• c_6 = {1,4}: 1,4 ∈ S' ✓

All 7 subsets are hit by S' = {1, 3, 4} with |S'| = 3 (optimal). No hitting set of size 2 exists (can be verified: no pair of elements covers all 7 subsets).

Suboptimal example: S'' = {0, 3, 4} (size 3) also hits all subsets but is not unique; S''' = {0, 1, 3, 5} (size 4) hits all subsets but is suboptimal.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; dual of MinimumSetCovering with planned VertexCover reduction
Non-trivial	✅ Pass	Distinct variable semantics and feasibility constraints from MinimumSetCovering
Correctness	⚠️ Warn	Abu-Khzam 2010 citation is misattributed; complexity section lacks a concrete best-known exact algorithm bound
Well-written	⚠️ Warn	Minor issues: decision vs optimization framing unclear; naming convention question

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

The problem does not currently exist in the codebase (pred show HittingSet fails). Hitting Set is one of Karp's 21 NP-complete problems (SP8 in Garey & Johnson) and is a well-established classical problem. The issue clearly identifies its relationship to Vertex Cover (special case) and Set Cover (dual), and having it in the reduction graph would enable natural reductions (e.g., VertexCover → HittingSet, HittingSet → ILP). The motivation is concrete and well-justified.

Both solver methods (brute-force and ILP reduction) are checked, which is good.

Non-trivial

Although Hitting Set is the LP dual of Set Cover, it is genuinely distinct as a computational model in this codebase:

• MinimumSetCovering: variables correspond to sets (which sets to select), objective is to minimize total weight of selected sets that cover all universe elements. It is an optimization problem.
• HittingSet (proposed): variables correspond to universe elements (which elements to select), constraint is that every set contains at least one selected element. Formulated as a satisfaction/decision problem with a budget K.

The variable domains, feasibility constraints, and problem type (satisfaction vs optimization) are all different. This is not a trivial renaming or variant of an existing problem.

Correctness

References verified:

1. Karp, 1972 — Verified. Hitting Set is indeed one of Karp's 21 NP-complete problems. The reference matches karp1972 already in docs/paper/references.bib. The claim that NP-completeness is proven via transformation from Vertex Cover matches Garey & Johnson A3 SP8.

2. Garey & Johnson, A3 SP8 — Verified. The "Full book text" section accurately reproduces the GJ formulation, including the comment that it remains NP-complete even when |c| ≤ 2 for all c ∈ C.

3. Abu-Khzam, 2010 — Misattributed. The issue claims "for 3-Hitting Set an O(2.270^k · n) algorithm is known (Abu-Khzam, 2010)." However, Abu-Khzam 2010 ("An improved kernelization algorithm for r-Set Packing", Information Processing Letters 110(16), pp. 621–624) is about kernelization for Set Packing, not a running-time bound for 3-Hitting Set. The O(2.270^k + n) algorithm for 3-Hitting Set is from Niedermeier & Rossmanith, 2003 ("An efficient fixed-parameter algorithm for 3-Hitting Set", Journal of Discrete Algorithms 1(1), pp. 89–102). The citation should be corrected.

4. W[2]-completeness — Verified. Hitting Set parameterized by solution size k is indeed W[2]-complete, which is a standard result in parameterized complexity theory.

Complexity section concern: The issue does not provide a concrete best-known exact algorithm with a specific time bound suitable for declare_variants!. It mentions brute-force O(2^|S|) and FPT algorithms, but the codebase requires a single complexity string like "2^universe_size" for the variant declaration. The brute-force bound of O(2^|S|) would work, but this should be stated more explicitly as the intended complexity string.

Well-written

Mostly good, with minor issues:

1. Decision vs optimization framing: The issue defines HittingSet as a satisfaction (decision) problem with a budget K, which is the GJ formulation. This is a valid design choice, but it should be made more explicit. The SatisfactionProblem trait uses Metric = bool, so the budget field becomes part of the instance. This is consistent, but the issue could clarify that this is intentionally a satisfaction problem (not MinimumHittingSet).

2. Schema field naming: The proposed universe_size and subsets fields are reasonable. Note that MinimumSetCovering uses universe_size and sets — using subsets here creates a slight inconsistency. Consider using sets for consistency, or document why subsets is preferred.

3. Example quality: The example is excellent — 6 elements, 7 subsets, budget K=3, with a "greedy trap" explanation and fully worked verification. This is exactly the level of detail needed for the paper.

4. All template sections present: Motivation, Name, Reference, Definition, Variables, Schema, Complexity, How to solve, and Example Instance are all substantive. No placeholder sections.

5. Symbol consistency: Symbols (S, C, K, S') are used consistently across sections.

Recommendations

• Fix the Abu-Khzam citation: Replace with Niedermeier & Rossmanith, 2003 for the 3-Hitting Set O(2.270^k) FPT result. Abu-Khzam 2010 can be cited separately for kernelization if desired.
• Add explicit complexity string: State that the intended declare_variants! complexity will be "2^universe_size" (brute-force over all element subsets).
• Consider naming subsets → sets for consistency with MinimumSetCovering, or document the distinction.
• Clarify satisfaction framing: Add a sentence noting this is intentionally a SatisfactionProblem (not MinimumHittingSet) to match the GJ formulation.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	Dual of existing MinimumSetCovering; satisfaction framing is distinct but value is debatable
Non-trivial	⚠️ Warn	Dual of Set Cover via incidence matrix transposition, but distinct variable semantics (picking elements vs. picking sets)
Correctness	❌ Fail	Abu-Khzam 2010 citation is misattributed; 2.270^k bound is from Niedermeier & Rossmanith
Well-written	✅ Pass	Complete template, good example, clear definition

Overall: 1 passed, 2 warnings, 1 failed

---

Usefulness

HittingSet does not currently exist in the codebase. However, MinimumSetCovering already exists and is the dual problem: every Hitting Set instance can be transformed to a Set Cover instance by transposing the incidence matrix (elements become sets, sets become universe elements). The transformation is O(|S| * |C|).

That said, the issue frames HittingSet as a satisfaction problem (with budget K, Metric = bool), while MinimumSetCovering is an optimization problem (Metric = SolutionSize). This is a genuinely different trait implementation. Additionally, Hitting Set is one of Karp's original 21 NP-complete problems (#15) and serves as a natural reduction target from Vertex Cover, which the issue correctly identifies.

The motivation mentions enabling reductions from Vertex Cover, which is reasonable since VC -> Hitting Set is a classical reduction (each edge becomes a 2-element subset). However, VC -> Set Cover already exists in the codebase. The added value depends on whether future reduction chains specifically need the Hitting Set formulation (element-picking rather than set-picking).

Non-trivial

Hitting Set and Set Cover are dual problems — this is well-established in the literature and acknowledged by the issue itself ("It is the dual of SET COVER"). The transformation between them is a straightforward incidence matrix transposition.

However, the two problems have genuinely different variable semantics:

• Set Cover: variables represent sets; x_i = 1 means "pick set i"
• Hitting Set: variables represent universe elements; x_i = 1 means "pick element i"

This means the dims(), evaluate(), and schema are structurally different (variables indexed over elements vs. over sets). It is not merely a type-cast or variant restriction. The issue proposes a satisfaction problem with a budget constraint, which is a different trait implementation than the existing optimization MinimumSetCovering.

Marking as Warn rather than Fail because there is a legitimate argument for both sides: it is the dual of an existing problem (suggesting redundancy), but it has different variable semantics and trait implementation (suggesting distinctness).

Correctness

Karp 1972: Correctly cited. Hitting Set is indeed one of Karp's 21 NP-complete problems, proven via transformation from Vertex Cover. The Garey & Johnson reference (A3 SP8) is also correct.

Abu-Khzam 2010 — MISATTRIBUTED: The cited paper "An improved kernelization algorithm for r-Set Packing" (Information Processing Letters 110(16), pp. 621-624) exists and is correctly bibliographically described. However, this paper is about r-Set Packing kernelization, NOT about Hitting Set FPT algorithms. The issue claims it provides an "FPT result for bounded-arity hitting set" with an "O(2.270^k * n) algorithm for 3-Hitting Set." This is incorrect:

• The O*(2.270^k) bound for 3-Hitting Set is from Niedermeier and Rossmanith (not Abu-Khzam).
• This bound has since been improved to O*(2.0755^k) by Wahlström, and further to O*(2.0409^k) in recent work.
• Abu-Khzam's 2010 paper improves the kernel size for r-Set Packing from O(k^r) elements to O(k^(r-1)) elements.

W[2]-completeness claim: Correct. Hitting Set parameterized by solution size k is indeed W[2]-complete, which is well-established in parameterized complexity theory.

Brute-force complexity claim: The O(2^|S| * |S| * |C|) bound is correct for exhaustive enumeration.

Recommendations

• Replace the Abu-Khzam 2010 citation with Niedermeier & Rossmanith (2003) for the 2.270^k FPT bound on 3-Hitting Set.
• Consider citing the improved bound of O*(2.0409^k) from recent work (2025).
• Add the declare_variants! complexity string: for general Hitting Set, brute-force is 2^universe_size; no better general exact algorithm is known beyond brute force (since W[2]-hard rules out FPT by solution size).

Well-written

Information completeness: All template sections are present and substantive. Motivation, Definition, Variables, Schema, Complexity, How to solve, and Example Instance are all filled in with real content.

Definition: Clear and follows the standard Garey & Johnson formulation. The decision problem framing (with budget K) is well-specified.

Symbol consistency: Symbols are consistent across sections. S, C, K, and S' are used consistently.

Schema: The field table is reasonable. universe_size, subsets, and budget are appropriate for a satisfaction problem. Note that size_fields for overhead expressions would need getter methods like universe_size() and num_subsets().

Example quality: The example with 6 elements and 7 subsets is non-trivial and fully worked. The "greedy trap" explanation adds pedagogical value. The optimal solution is verified step by step.

Minor note: The naming HittingSet (no prefix) is correct for a satisfaction problem per project conventions.

[GiggleLiu]

Fix-issue changelog

• Renamed HittingSet → MinimumHittingSet: reframed as OptimizationProblem (minimize |S'|) per project conventions; removed budget field
• Fixed misattributed citation: replaced Abu-Khzam 2010 (r-Set Packing kernelization) with Niedermeier & Rossmanith 2003 for the O*(2.270^k) 3-Hitting Set FPT bound; added Tsur 2025 (O*(2.0409^k)) as current best
• Added explicit complexity string: "2^universe_size" for declare_variants!
• Renamed field subsets → sets for consistency with MinimumSetCovering
• Strengthened motivation: added paragraph explaining why both MinimumHittingSet and MinimumSetCovering are valuable despite LP duality (different variable semantics, downstream reduction targets)
• Updated related rule issue titles: [Rule] MinimumVertexCover to MinimumHittingSet #200, [Rule] MinimumHittingSet to AdditionalKey #460, [Rule] MinimumHittingSet to BoyceCoddNormalFormViolation #462, [Rule] MinimumHittingSet to SafetyOfDatabaseTransactionSystems #467 renamed to use MinimumHittingSet
• Added BF complexity estimate and suboptimal example to Example section

Applied by /fix-issue.