[Rule] MinimumVertexCover to MinimumHittingSet

[isPANN]

Source: MinimumVertexCover (unit-weight / cardinality variant)
Target: MinimumHittingSet
Motivation: Establishes NP-completeness of HITTING SET via polynomial-time reduction from VERTEX COVER, showing that every graph edge can be viewed as a 2-element subset to be "hit", making HITTING SET a strict generalization of VERTEX COVER.

Reference: Garey & Johnson, Computers and Intractability, Section 3.2.1, p.64

Scope

This reduction is between the unweighted (unit-weight) Vertex Cover and the cardinality Hitting Set.
The source type is MinimumVertexCover<SimpleGraph, One> (weight type One, minimising vertex count)
and the target type is MinimumHittingSet (minimising number of elements selected).

A reduction from the weighted MinimumVertexCover<SimpleGraph, i32> to MinimumHittingSet would be unsound: the target problem has no weight field, so vertex weights cannot be preserved and the optimal cardinality of the hitting set does not equal the optimal weight of the vertex cover when weights differ from 1.

Prerequisite: Add MinimumVertexCover<SimpleGraph, One> to the declare_variants! block in
src/models/graph/minimum_vertex_cover.rs. This can be done in the same PR as the rule itself.

Reduction Algorithm

(2) HITTING SET
INSTANCE: Collection C of subsets of a set S, positive integer K.
QUESTION: Does S contain a hitting set for C of size K or less, that is, a subset S' ⊆ S with |S'| <= K and such that S' contains at least one element from each subset in C?

Proof: Restrict to VC by allowing only instances having |c|=2 for all c E C.

Summary:
Given a MinimumVertexCover instance (G, k) where G = (V, E) with unit weights, construct a HittingSet instance as follows:

1. Universe construction: The universe S = V (one element per vertex). The universe has |V| = n elements.
2. Collection construction: For each edge {u, v} ∈ E, add the 2-element subset {u, v} to the collection C. Each edge becomes exactly one subset of size 2. The collection has |E| = m subsets.
3. Budget parameter: Set K' = k (the target hitting-set size equals the vertex-cover budget).
4. Solution extraction: A hitting set H ⊆ V of size ≤ k hits every subset {u, v} ∈ C if and only if H contains at least one of u, v for every edge {u, v} ∈ E — which is exactly the vertex cover condition.

Key invariant: Every vertex cover for G is a hitting set for C (and vice versa), because each subset in C corresponds to exactly one edge in G and has size 2. Because both problems use unit weights / cardinality objectives, the optimal values are equal.

Size Overhead

Symbols:

• n = num_vertices of source graph G (getter on MinimumVertexCover<SimpleGraph, One>)
• m = num_edges of source graph G (getter on MinimumVertexCover<SimpleGraph, One>)

Target metric (code name)	Polynomial (using symbols above)
universe_size	num_vertices
num_sets	num_edges

Derivation:

• Universe: one element per vertex in G → |S| = n
• Collection: one 2-element subset per edge in G → |C| = m
• Each subset has exactly size 2 (one per edge endpoint)
• Budget parameter is passed through unchanged: K' = k

Validation Method

• Closed-loop test: reduce a MinimumVertexCover<SimpleGraph, One> instance to MinimumHittingSet, solve the HittingSet with BruteForce, extract the hitting set H, verify H is a valid vertex cover on the original graph
• Check that the minimum hitting set size equals the minimum vertex cover size on the same graph
• Test with a graph where greedy vertex selection fails (e.g., a star K_{1,5}) to ensure optimality is required
• Verify that adding a non-edge subset to C would break the correspondence (i.e., the restriction to 2-element edge sets is what makes the two problems equivalent)

Example

Source instance (MinimumVertexCover<SimpleGraph, One>):
Graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 8 edges:

• Edges: {0,1}, {0,2}, {1,3}, {2,3}, {2,4}, {3,5}, {4,5}, {1,4}
• (A graph with chords — non-trivial structure requiring careful cover selection)
• Minimum vertex cover: k = 3, for example {0, 3, 4} covers:
  • {0,1} by 0 ✓, {0,2} by 0 ✓, {1,3} by 3 ✓, {2,3} by 3 ✓
  • {2,4} by 4 ✓, {3,5} by 3 ✓, {4,5} by 4 ✓, {1,4} by 4 ✓
• Alternative optimal: {1, 2, 5} (also size 3)
• Suboptimal example: {1, 2, 3, 4} is a valid cover of size 4 but not minimal

Constructed target instance (MinimumHittingSet):
Universe S = {0, 1, 2, 3, 4, 5} (same 6 vertices)
Collection C (one 2-element subset per edge):

• {0, 1}, {0, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 5}, {4, 5}, {1, 4}

Budget K' = 3

Solution mapping:

• Minimum hitting set: H = {0, 3, 4}
• Verification against each subset in C:
  • {0,1}: 0 ∈ H ✓
  • {0,2}: 0 ∈ H ✓
  • {1,3}: 3 ∈ H ✓
  • {2,3}: 3 ∈ H ✓
  • {2,4}: 4 ∈ H ✓
  • {3,5}: 3 ∈ H ✓
  • {4,5}: 4 ∈ H ✓
  • {1,4}: 4 ∈ H ✓
• All 8 subsets are hit, |H| = 3 = K' ✓
• Extracted vertex cover in G: {0, 3, 4} — same as hitting set ✓

Round-trip verification (brute-force):

• Total configurations: 2⁶ = 64
• Feasible vertex covers: 16
• Optimal (size 3): 2 solutions — {0,3,4} and {1,2,5}
• Suboptimal feasible: 14 (sizes 4, 5, 6)

Greedy trap: Vertices 1, 2, 3, 4 each have degree 3 while vertices 0 and 5 have degree 2. A greedy algorithm picking highest-degree vertices might select {1, 2, 3} which misses edge {4,5}. The optimal solution {0, 3, 4} includes the low-degree vertex 0, demonstrating that degree-greedy is not optimal.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	⚠️ Warn	Hitting Set is the well-known dual of Set Cover; codebase already has MinimumSetCovering. Proposed reduction duplicates existing VC -> MinimumSetCovering path under a different name.
Non-trivial	❌ Fail	The reduction is a restriction/subtype coercion — vertices map 1-to-1 to universe elements, edges map 1-to-1 to 2-element subsets, with no structural transformation.
Correctness	✅ Pass	Garey & Johnson Section 3.2.1 correctly uses restriction to prove Hitting Set NP-complete from Vertex Cover. Reference is accurate.
Well-written	⚠️ Warn	Issue is well-structured overall, but overhead field names (universe_size, num_sets) reference a non-existent HittingSet model. Minor: the reduction is described as a "restriction" proof in the GJ quote but then presented as a constructive reduction in the summary.

Overall: 1 passed, 1 failed, 2 warnings

---

Usefulness

The target problem "HittingSet" does not currently exist in the codebase. However, Hitting Set is the well-known dual of Set Cover — they are exactly the same problem with rows and columns of the incidence matrix transposed (Wikipedia: Set Cover). The codebase already implements MinimumSetCovering, which means adding a HittingSet model would introduce a mathematically equivalent problem under a different name.

Furthermore, the existing reduction MinimumVertexCover -> MinimumSetCovering already captures the same structural relationship: edges become universe elements and vertex neighborhoods become sets. The proposed VC -> HittingSet reduction (edges become sets, vertices become universe elements) is just the transposed view of the same correspondence.

In Karp's original reduction tree, the path is Vertex Cover -> Set Covering -> Hitting Set, where the Set Covering -> Hitting Set step is simply the duality transformation. The proposed direct VC -> Hitting Set reduction does not provide a shorter or lower-overhead path — it provides a different encoding of the same relationship.

Non-trivial

The issue's own Garey & Johnson quote is explicit: "Restrict to VC by allowing only instances having |c|=2 for all c in C." This is a textbook restriction proof — the weakest form of NP-completeness reduction. The construction involves:

• Vertices map 1-to-1 to universe elements (no new elements)
• Edges map 1-to-1 to 2-element subsets (no gadgets, no auxiliary structure)
• Budget parameter passes through unchanged (K' = k)
• Solution extraction is the identity mapping

There is no gadget construction, no penalty terms, no auxiliary variables, and no non-trivial structural transformation. Every vertex cover is literally the same set as the corresponding hitting set. This meets the skill's definition of subtype coercion: "The reduction merely casts to a more general type with no structural change to the problem instance." Vertex Cover instances are simply Hitting Set instances where all subsets happen to have size exactly 2.

Correctness

The reference to Garey & Johnson, Computers and Intractability, Section 3.2.1 is accurate. Section 3.2 ("Restriction") describes the restriction technique for proving NP-completeness, and Hitting Set (problem SP8 in GJ's appendix) is indeed proved NP-complete by restriction from Vertex Cover. The mathematical claims in the issue are correct: a vertex cover for G is a hitting set for the collection of edge-subsets, and vice versa.

The garey1979 entry already exists in the project bibliography (docs/paper/references.bib), confirming this is a known and verified source.

Well-written

Strengths:

• All required template sections are present and substantive
• The example is non-trivial (6 vertices, 8 edges) and fully worked
• The validation method is concrete and actionable
• Symbols are defined before use and consistent across sections

Issues:

• The overhead table references field names universe_size and num_sets, but these are MinimumSetCovering getter names. Since HittingSet does not exist as a model, these field names are unverifiable. The issue should specify what the HittingSet model's schema would look like, or reference an existing [Model] issue for HittingSet.
• There is a tension between the GJ quote (which describes a restriction proof, i.e., showing VC is a special case of Hitting Set) and the summary (which presents it as a constructive reduction from VC to Hitting Set). While both directions hold due to the equivalence, the framing is inconsistent.
• The "Reduction Algorithm" section quotes GJ's restriction proof verbatim but then provides a constructive summary — the relationship between these two framings should be clarified.

Recommendations

• Consider whether HittingSet should be a separate model at all. Since Hitting Set is the exact dual of Set Cover, it may be better to add a note or alias to MinimumSetCovering rather than creating a duplicate problem. If HittingSet is added as a distinct model, the issue should explain why the dual perspective justifies a separate type.
• If proceeding, file a [Model] issue for HittingSet first. The reduction cannot be implemented without the target problem existing.
• The existing VC -> MinimumSetCovering reduction already captures this relationship (with rows/columns transposed). Consider whether the additional reduction provides value beyond what exists.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	❌ Fail	Target problem "HittingSet" does not exist in the codebase; equivalent reduction to MinimumSetCovering already exists
Non-trivial	❌ Fail	Reduction is a restriction/subtype coercion, not a structural transformation
Correctness	⚠️ Warn	Reference is valid but the reduction direction described is inverted from what the source actually proves
Well-written	⚠️ Warn	Algorithm is clear but target problem does not exist; overhead metrics reference non-existent problem fields

Overall: 0 passed, 2 failed, 2 warnings

---

Usefulness

The target problem HittingSet does not exist in the codebase. Before this rule could be implemented, a [Model] issue for HittingSet would need to be filed and implemented first.

More importantly, Hitting Set is mathematically equivalent to Set Cover (they are dual formulations — see Garey & Johnson Section 3.1.2). The codebase already has MinimumSetCovering, and there is already a direct reduction MinimumVertexCover → MinimumSetCovering with overhead (num_sets = num_vertices, universe_size = num_edges).

The proposed reduction maps vertices → universe elements and edges → subsets (universe_size = num_vertices, num_sets = num_edges). Even if HittingSet were implemented as a separate problem, this reduction would be redundant with the existing MinimumVertexCover → MinimumSetCovering path (since Set Cover and Hitting Set are equivalent up to transposition).

Non-trivial

The reduction described in this issue is a restriction proof, not a gadget-based reduction. The Garey & Johnson reference (Section 3.2.1, p.64) explicitly states:

"Restrict to VC by allowing only instances having |c|=2 for all c ∈ C."

This means Vertex Cover is a special case of Hitting Set (where all subsets have size 2). The "reduction" in the issue summary simply observes that a graph's edge set naturally forms a collection of 2-element subsets — each edge {u,v} becomes a subset {u,v}. There is:

• No gadget construction — edges map directly to subsets with no auxiliary elements
• No structural transformation — the universe is exactly the vertex set, subsets are exactly the edges
• Identity budget — K' = k with no modification
• Identity solution extraction — the hitting set IS the vertex cover, unchanged

This is a subtype coercion: a Vertex Cover instance IS a Hitting Set instance by definition. The issue itself acknowledges this equivalence ("Every vertex cover for G is a hitting set for C (and vice versa)").

Correctness

The reference Garey & Johnson, Computers and Intractability, Section 3.2.1, p.64 is a valid, well-known source. It is already in the project bibliography (garey1979 in docs/paper/references.bib).

However, there is a directional confusion. The G&J proof shows Hitting Set is NP-complete by restriction from Vertex Cover — meaning Vertex Cover is a special case OF Hitting Set, not the other way around. In Karp's reduction tree (as recorded in references.md), the chain is:

Vertex Cover → Set Covering → Hitting Set

The issue presents this as a "reduction from Vertex Cover to Hitting Set," but what it actually describes is the trivial observation that VC instances are already HittingSet instances. This is not a polynomial-time many-one reduction in the usual Karp sense — it is a restriction (subset relationship between problem instances).

Well-written

The algorithm section is clearly written and the example is well-constructed with verification steps. However:

• Target problem does not exist: The overhead table references universe_size and num_sets as target metrics, but there is no HittingSet problem type to validate these against.
• Confusion between restriction and reduction: The quoted G&J text says "Restrict to VC" which proves NP-hardness of Hitting Set by showing VC ⊆ HittingSet. The summary section then describes the forward mapping (VC → HS), which is correct procedurally but is the trivial direction.
• Symbols are well-defined and consistent across sections.
• Example is non-trivial (6 vertices, 8 edges) and fully worked.

Recommendations

1. This issue should likely be closed as redundant. The codebase already handles the Vertex Cover → Set Cover reduction, and Hitting Set is the dual of Set Cover. If a HittingSet model is desired, it should be filed as a separate [Model] issue first, and the relationship to MinimumSetCovering should be clarified (are they separate problems or aliases?).

2. If the goal is to have a Hitting Set problem in the graph, consider instead filing a [Model] issue for HittingSet and then implementing the Set Covering ↔ Hitting Set duality transformation, which would be a more meaningful and non-trivial reduction.

[isPANN]

Issue Quality Check — Rule (Re-check)

Check	Result	Details
Usefulness	✅ Pass	MinimumHittingSet exists but is an orphan node (0 reductions) — this would be the first connection
Non-trivial	✅ Pass	Connects a disconnected problem to the graph (orphan exception)
Correctness	✅ Pass	Garey & Johnson 1979, Section 3.2.1 confirmed; reference in project bibliography
Well-written	❌ Fail	Example claims minimum vertex cover k=4, but actual minimum is k=3

Overall: 3 passed, 1 failed, 0 warnings

Previously (2026-03-11): 0 passed, 2 failed, 2 warnings → Now: 3 passed, 1 failed. Key change: MinimumHittingSet now exists in the codebase as an orphan node, resolving previous Useless and Trivial failures.

---

Usefulness

Since the last check, MinimumHittingSet has been added to the codebase but has zero reductions — it is an isolated (orphan) node in the reduction graph. This proposed reduction would be the first connection, linking it to MinimumVertexCover and thereby to the rest of the graph.

The existing reduction MinimumVertexCover → MinimumSetCovering (overhead: num_sets = num_vertices, universe_size = num_edges) maps to a different target. While Set Cover and Hitting Set are dual problems, they are separate models in this codebase with different schemas and different semantic interpretations (Set Cover selects sets to cover the universe; Hitting Set selects universe elements to hit every set). The proposed reduction provides a distinct path with different overhead dimensions (universe_size = num_vertices, num_sets = num_edges — transposed from the Set Cover reduction).

Non-trivial

The reduction is structurally simple — vertices map 1:1 to universe elements, edges map 1:1 to 2-element subsets, and the budget passes through unchanged. The G&J proof explicitly calls this a "restriction" (the weakest form of NP-completeness proof).

However, per the check-issue policy: "if a trivial reduction makes originally disconnected problems connected, it is also Pass." MinimumHittingSet is currently an orphan with no incoming or outgoing reductions. This reduction would connect it to the graph, satisfying this exception.

Correctness

Garey & Johnson, Computers and Intractability, Section 3.2.1, p.64 — confirmed. The garey1979 entry exists in docs/paper/references.bib. The mathematical claims are accurate: a vertex cover for G is a hitting set for the collection of edge-subsets, and vice versa. The overhead formulas (universe_size = num_vertices, num_sets = num_edges) are correct and match the target problem's size_fields.

Note: the G&J text describes a restriction proof (VC is a special case of Hitting Set), while the issue summary presents the constructive forward mapping. Both directions hold, and the constructive direction is what would be implemented as a ReduceTo implementation.

Well-written

Strengths:

• All required template sections are present and substantive
• Algorithm is clear and step-by-step
• Overhead field names (universe_size, num_sets) correctly match MinimumHittingSet's size_fields
• Symbols are defined and consistent across sections
• Validation method is concrete

Failures:

• ❌ Example claims wrong optimal value. The issue states minimum vertex cover k = 4 with solution {1, 2, 3, 4}. Python brute-force verification shows the actual minimum is k = 3, with optimal solutions {0, 3, 4} and {1, 2, 5}. The set {1, 2, 3, 4} is a valid vertex cover but is suboptimal (size 4, not 3). This error propagates to the target instance: the minimum hitting set is also 3, not 4.

  Verification stats:

  • Total vertex covers: 16 (out of 64 subsets)
  • Optimal vertex covers (size 3): 2 — {0,3,4} and {1,2,5}
  • Suboptimal feasible covers: 14 (satisfies round-trip complexity requirement)
  • Round-trip confirmed: optimal VC solutions = optimal HS solutions (after fixing the example)

Recommendations

1. Fix the example — correct the minimum vertex cover to k = 3 with solution {0, 3, 4} or {1, 2, 5}, and update the target HittingSet instance accordingly.
2. Consider adding a note about the relationship between this reduction and the existing MVC → MinimumSetCovering reduction, explaining why both are valuable (different target problems, transposed overhead dimensions).