[Rule] MinimumDominatingSet/One to MinimumHittingSet

[isPANN]

Source

MinimumDominatingSet/SimpleGraph/One

Target

MinimumHittingSet

Motivation

This closed-neighborhood equivalence gives the unit-weight Dominating Set variant a direct path to Hitting Set. The unit-weight restriction is explicit and necessary because the target model has no weights.

Reference

Garey and Johnson, Computers and Intractability, 1979, Appendix A (Dominating Set and Hitting Set definitions). The construction is an immediate incidence formulation of the two definitions.

Reduction Algorithm

Given G=(V,E), V={0,...,n-1}:

1. Use V as the target universe.
2. For every vertex v, create one target set N[v].
3. A target hitting-set configuration maps identically to the selected source vertices.

For S subseteq V, hitting every N[v] means S intersect N[v] is nonempty for every v, precisely the condition that every vertex is selected or adjacent to a selected vertex. Cardinalities are identical.

Size Overhead

Target metric	Formula
universe_size	num_vertices
num_sets	num_vertices

Validation Method

• Exhaust every simple graph through four vertices and compare minimum dominating-set and hitting-set cardinalities.
• Include empty graphs, isolated vertices, paths, cycles, stars, and complete graphs.
• Check identity extraction for every optimal target configuration.

Example

1. Source instance: path 0-1-2-3-4 with unit weights.
2. Construction: universe {0,1,2,3,4} with family [{0,1},{0,1,2},{1,2,3},{2,3,4},{3,4}].
3. Target instance: Minimum Hitting Set on these five closed neighborhoods.
4. Round trip: {1,3} hits every neighborhood and maps to a dominating set of size 2. No singleton works; configurations {0,2,4} and {0,1,3} are feasible but suboptimal. Exhaustive enumeration confirms optimum 2.

BibTeX

@book{GareyJohnson1979,
  author = {Garey, Michael R. and Johnson, David S.},
  title = {Computers and Intractability: A Guide to the Theory of NP-Completeness},
  publisher = {W. H. Freeman},
  year = {1979}
}

[isPANN]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	No existing path from MinimumDominatingSet/SimpleGraph/One to MinimumHittingSet
Non-trivial	✅ Pass	Converts graph-domination constraints into a closed-neighborhood hypergraph with one target set per source vertex
Correctness	✅ Pass	The cited definitions were verified, and independent primary literature states the exact closed-neighborhood equivalence
Completeness	✅ Pass	The construction has no graph-side precondition; all traced legitimate edge cases preserve feasibility and cardinality
Well-written	✅ Pass	All required sections, symbols, target metrics, extraction, and a nontrivial round-trip example are present and consistent

Overall: 5 passed, 0 failed, 0 warnings

---

Usefulness

Both endpoints resolve in the current catalog. The source resolves specifically as MinimumDominatingSet {graph: SimpleGraph, weight: One} and the target as MinimumHittingSet; the latter exposes the exact size fields universe_size and num_sets used by the issue. pred path MinimumDominatingSet/SimpleGraph/One MinimumHittingSet --json reports no existing reduction path, so the proposed edge is new rather than dominated by a composite path.

The motivation is substantive: the restriction to unit weights is necessary because MinimumHittingSet minimizes cardinality and has no element-weight field.

Non-trivial

Although solution coordinates are preserved one-to-one, this is not an identity or subtype coercion. It changes the instance structure: from an undirected graph and domination relation to a set system whose constraints are the closed neighborhoods N[v]. The construction is explicit and directly implementable.

Correctness

• Garey and Johnson (1979) is present in docs/paper/references.bib. The scanned book was checked directly: Appendix A, GT2 on book p. 190 defines Dominating Set, and SP8 on book p. 222 defines Hitting Set. These definitions support the issue's two problem statements, but the book entries do not themselves present this direct reduction.
• Stronger direct support is available in Bannach and Tantau, Computing Hitting Set Kernels By AC⁰-Circuits, STACS 2018, Introduction p. 9:2, DOI 10.4230/LIPIcs.STACS.2018.9: it states that a dominating set is exactly a hitting set of the hypergraph whose hyperedges are the vertices' closed neighborhoods.
• Independent corroboration appears in Grobler and Siebertz, The PACE 2025 ... Challenge: Dominating Set and Hitting Set, IPEC 2025, Section 2, DOI 10.4230/LIPIcs.IPEC.2025.32. It defines the same closed-neighborhood formulation and explains the standard polynomial equivalence among Dominating Set, Set Cover, and Hitting Set.

The proof is immediate for the repository's undirected graph model: for any S ⊆ V, S hits every N[v] iff for every v there is an s ∈ S with s ∈ N[v]; symmetry of undirected adjacency makes this equivalent to v ∈ N[s], i.e. S dominates every vertex. The selected elements and cardinality are unchanged.

The worked path example was also checked: the five listed closed neighborhoods are correct, {1,3} is feasible with value 2, no singleton dominates the path, and the two stated larger configurations are feasible but suboptimal. The existing exhaustive validation script checked this rule over every ordinary simple graph through four vertices and confirmed all ten candidate-rule examples.

Completeness

Literature scope. Bannach–Tantau state the equivalence for a graph without a connectivity, minimum-degree, regularity, or cardinality restriction. Their observation is definitional, and its proof does not depend on an NP-completeness promise. Garey–Johnson's Appendix entries use finite undirected graphs/set systems and introduce no restriction relevant to the construction.

Codebase scope. pred show confirms that the source has size fields num_vertices and num_edges; the One variant has exactly one binary coordinate per vertex. SimpleGraph::new can construct empty/disconnected graphs and, at the constructor level, does not reject self-loops or parallel edges. MinimumDominatingSet::closed_neighborhood inserts the vertex itself and deduplicates neighbors. MinimumHittingSet::new accepts an empty universe/family and deduplicates elements within target sets.

Hand traces beyond the worked example:

1. Empty graph (V = ∅). The construction yields universe size 0 and no target sets. The empty target configuration hits the empty family, extracts identically, and is the unique size-0 dominating configuration.
2. One isolated vertex. The construction yields universe {0} and family [{0}]. The only feasible hitting set is {0}, which extracts to the only dominating set; both optima are 1.
3. Self-loop and parallel-edge inputs admitted by the constructor. A self-loop only repeats v inside N[v], and parallel edges only repeat an existing neighbor; set deduplication removes both repetitions. The target remains valid and identity extraction preserves the same dominating set.

For comparison with existing source-adjacent code, minimumdominatingset_ilp.rs also creates one closed-neighborhood constraint per vertex without special-case graph assumptions. The existing minimumvertexcover_minimumhittingset.rs uses the same universe-coordinate/identity-extraction convention. The proposed construction matches those edge-input and extraction behaviors.

Well-written

All required template sections are present and substantive. G=(V,E) and n are defined before use; the overhead formulas use the source getter num_vertices and exact target getters universe_size/num_sets; solution extraction is explicit. The five-vertex path example exercises overlapping neighborhoods, has multiple feasible solutions of different values, and is small enough for a closed-loop exhaustive check.

Recommendations

• Add the Bannach–Tantau STACS 2018 citation (DOI above) to the issue's Reference/BibTeX sections. It directly supports the proposed reduction, whereas the current Garey–Johnson citation supports only the endpoint definitions.
• Optionally state in the algorithm that closed neighborhoods are interpreted as sets, making duplicate adjacency entries immaterial.

[isPANN]

Rule Fix

Diagnosis:

• All 12 structured checks pass. The reduction direction, both directions of the equivalence, identity extraction, polynomial construction, exact overhead, Min-to-Min objective preservation, example, and target validity are consistent.
• No undirected rerouting risk applies: the target is a set system and the construction has no path gadgets or directional assumptions.
• No mathematical defect was found, so the issue body was not changed.

Literature:

• Garey and Johnson (1979) supports the endpoint definitions used by the issue.
• Bannach and Tantau, Computing Hitting Set Kernels By AC⁰-Circuits (STACS 2018), DOI 10.4230/LIPIcs.STACS.2018.9, states the exact canonical equivalence: a dominating set is a hitting set of the hypergraph of closed neighborhoods. The issue's construction matches it.
• Grobler and Siebertz, The PACE 2025 Parameterized Algorithms and Computational Experiments Challenge: Dominating Set and Hitting Set (IPEC 2025), DOI 10.4230/LIPIcs.IPEC.2025.32, independently corroborates the closed-neighborhood incidence construction.

Changes:

• None required; the original algorithm is sound as written.

Smoke test:

• 87 named checks passed across the required buckets, plus per-configuration feasibility and extraction checks.
• Exhaustively checked all 76 labeled simple graphs on 0 through 4 vertices.
• Confirmed objective equality, identity extraction, the five-vertex path example, four boundary instances, five overhead spot-checks, and target validity for every constructed instance.

[isPANN]

Issue Quality Re-check — Rule

The issue body is unchanged since the prior quality check. This mandatory post-diagnosis re-check confirms the earlier result.

Check	Result	Details
Usefulness	✅ Pass	No existing reduction path from MinimumDominatingSet/SimpleGraph/One to MinimumHittingSet
Non-trivial	✅ Pass	Converts graph domination constraints into a closed-neighborhood set system
Correctness	✅ Pass	The construction matches direct primary literature and passed exhaustive smoke testing
Completeness	✅ Pass	Covers all source instances admitted by the model, including empty and disconnected graphs
Well-written	✅ Pass	Required sections, exact target metrics, extraction, notation, and worked example are complete

Overall: 5 passed, 0 failed, 0 warnings

Usefulness

Both endpoint variants resolve in the catalog, and pred path reports no existing path. The unit-weight restriction is necessary because MinimumHittingSet minimizes cardinality and has no element weights.

Non-trivial

The solution coordinates are preserved, but the instance structure is not: each graph vertex becomes a universe element and each closed neighborhood becomes a target set. This is a direct, implementable structural transformation.

Correctness

Garey and Johnson (1979) supports the endpoint definitions. Bannach and Tantau (STACS 2018), DOI 10.4230/LIPIcs.STACS.2018.9, directly states that a dominating set is exactly a hitting set of the hypergraph of closed neighborhoods. Grobler and Siebertz (IPEC 2025), DOI 10.4230/LIPIcs.IPEC.2025.32, independently describes the same incidence construction. For every S ⊆ V, S hits every N[v] iff every v is selected or adjacent to a selected vertex, and the cardinality is unchanged.

The smoke test exhaustively checked all 76 labeled simple graphs through four vertices, all binary configurations on those graphs, identity extraction for every feasible target witness, and objective equality.

Completeness

The proof has no connectivity, degree, or size precondition. Code inspection confirms that source closed neighborhoods always include the vertex and deduplicate adjacency entries, while the target constructor validates universe membership and deduplicates set elements. The construction handles the empty graph (U = ∅, no sets), isolated vertices (N[v] = {v}), disconnected graphs, loops, and repeated adjacency entries without losing information. The existing Dominating Set to ILP rule uses the same one-closed-neighborhood-constraint-per-vertex semantics.

Well-written

All required sections are substantive. Symbols are defined before use, overhead metrics match the target's universe_size and num_sets getters, identity extraction is explicit, and the five-vertex path example contains optimal and multiple suboptimal feasible solutions.

Recommendation

• Optionally add the Bannach–Tantau citation to the issue body because it states the direct equivalence, while the current Garey–Johnson citation supplies the endpoint definitions.