[Rule] MinimumDominatingSet/i32 to MinimumSetCovering/i32

[isPANN]

Source

MinimumDominatingSet/SimpleGraph/i32

Target

MinimumSetCovering/i32

Motivation

This standard closed-neighborhood formulation connects weighted Dominating Set directly to weighted Set Covering. The graph currently has no path between these models, and the construction preserves arbitrary signed integer vertex weights supported by both implementations.

Reference

Garey and Johnson, Computers and Intractability, 1979, Appendix A (Dominating Set and Set Covering definitions). The closed-neighborhood construction below follows directly from the definitions.

Reduction Algorithm

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

1. Set the target universe to V.
2. For each vertex v, create the set D_v=N[v]={v} union {u:{u,v} in E}.
3. Give D_v weight w_v.
4. Selecting target set D_v maps back to selecting graph vertex v.

A vertex set S dominates G iff union_{v in S} N[v]=V, which is exactly the target covering constraint. The objective is identical because weights are copied entry by entry. Isolated vertices and the empty graph are handled by the same construction. Self-loops and repeated edges, which SimpleGraph can represent, do not change the construction because each N[v] is treated as a set.

Size Overhead

Target metric	Formula
universe_size	num_vertices
num_sets	num_vertices

Validation Method

• Exhaustively compare weighted optimum values on every simple graph through four vertices, including negative weights and isolated vertices.
• Verify every optimal target configuration maps to a dominating source configuration with the same value.
• The temporary exhaustive checker also validates the canonical weighted path below.

Example

1. Source instance: path 0-1-2-3-4 with weights [3,1,4,1,3].
2. Construction: target universe {0,1,2,3,4} and sets
   • D_0={0,1} weight 3,
   • D_1={0,1,2} weight 1,
   • D_2={1,2,3} weight 4,
   • D_3={2,3,4} weight 1,
   • D_4={3,4} weight 3.
3. Target instance: weighted Minimum Set Covering with the sets above.
4. Round trip: {D_1,D_3} covers the universe with value 2 and maps to dominating set {1,3} of value 2. Choices such as {D_0,D_3} are feasible but suboptimal, so the example checks both feasibility and weight preservation.

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	Both variants resolve in pred, and pred path MinimumDominatingSet MinimumSetCovering --json reports no existing path.
Non-trivial	✅ Pass	The construction changes a graph instance into a set system by creating one closed-neighborhood set per vertex; it is not a subtype cast, identity, or variable relabeling.
Correctness	✅ Pass	Garey–Johnson's cited definitions are real and consistent with the issue; an independent source explicitly proves the same closed-neighborhood reduction. Copying weights one-to-one preserves every feasible solution's objective, including signed i32 weights.
Completeness	⚠️ Warn	The construction works on all traced legal inputs, but the body documents only empty graphs and isolated vertices. The repository's SimpleGraph constructor also permits self-loops and parallel edges; please state that neighborhood deduplication handles them.
Well-written	✅ Pass	All required sections are substantive, target metric names match pred show, the algorithm and extraction are implementable, and the five-vertex weighted example is non-degenerate.

Overall: 4 passed, 0 failed, 1 warning

---

Usefulness

• pred show MinimumDominatingSet --json resolves the default source as {graph: SimpleGraph, weight: i32} with size fields num_vertices and num_edges.
• pred show MinimumSetCovering --json resolves the target as {weight: i32} with size fields num_sets and universe_size.
• pred path MinimumDominatingSet MinimumSetCovering --json reports no reduction path. The proposed edge therefore adds graph connectivity rather than duplicating a direct or composite route.
• The motivation is concrete: it exposes the standard structural correspondence directly and preserves the repository's signed integer objective without routing through a different representation.

Non-trivial

For each vertex v, the algorithm constructs a target set D_v = N[v] over a newly defined universe V. The target covering constraints are induced by graph adjacency, and the graph's vertex costs become set costs. This is a genuine representation change with newly constructed constraints, while retaining a clear one-to-one witness map.

Correctness

• Garey and Johnson, Computers and Intractability (1979), exists and is already present in docs/paper/references.bib as garey1979. Appendix A1, printed p. 190, defines DOMINATING SET for an unrestricted graph G=(V,E); Appendix A3.1, printed p. 222, defines MINIMUM COVER over a finite set. Those entries support the two source/target definitions, as the issue claims. They do not themselves present this particular reduction or its signed weighted extension, so they should not be described as the proof source.
• Independent cross-check: the UMass COMPSCI 311 solution, Problem 8(a), explicitly starts from an arbitrary Dominating Set instance, takes universe V, and creates S_v={v}∪N_v; it proves the iff correspondence and polynomial construction time.
• The weighted extension follows exactly: selecting target set D_v and selecting source vertex v use the same binary coordinate and copied weight w_v. Thus every corresponding feasible configuration has exactly the same sum. No positivity assumption is used, so zero, negative, and mixed i32 weights remain valid.
• The supplied validation script completed successfully: validated 10 candidate rules and all canonical examples. The path example's {D_1,D_3} has cost 2 and maps to {1,3}; feasible alternatives such as {D_0,D_3} and {D_1,D_4} have cost 4, so the example distinguishes the optimum from multiple suboptimal covers.

No lower-overhead construction was found: num_sets = num_vertices is intrinsic to the one-set-per-vertex witness mapping, while universe_size = num_vertices follows the standard reduction.

Completeness

Literature scope. The UMass proof says to begin with an arbitrary Dominating Set instance and introduces no connectedness, minimum-degree, or simplicity precondition. Garey–Johnson's Appendix definition likewise states a general graph instance. The signed weighted extension does not narrow the domain because the construction preserves the objective term-by-term.

Codebase scope. MinimumDominatingSet<SimpleGraph, i32> accepts any vertex count with a matching Vec<i32>; weights may be zero, negative, or mixed. SimpleGraph::new checks endpoint range but does not reject self-loops or repeated edges. MinimumDominatingSet::closed_neighborhood collects neighbors into a HashSet, so repeated adjacency is harmless.

Hand traces beyond the worked example:

1. Empty graph: V=∅, E=∅, weights=[] produces universe ∅, no sets, and no weights. The empty target configuration covers the empty universe with value 0 and maps to the empty source configuration, which vacuously dominates the empty graph with value 0.
2. Single isolated vertex: for V={0}, E=∅, w_0=-5, the construction creates universe {0} and D_0={0} of weight -5. Every cover must select D_0; extraction selects vertex 0, the unique dominating set, with the same value -5.
3. Self-loop/parallel-edge input permitted by the code: neighborhood collection collapses repeated appearances and v is inserted once into N[v]. The resulting target sets therefore express exactly the same domination relation; extraction remains coordinate-wise and loses no information.

The issue already states that empty graphs and isolated vertices are handled, but it does not mention the third legitimate code-level case. That documentation gap is a warning, not a semantic failure.

Existing same-source rules inspected:

• src/rules/minimumdominatingset_ilp.rs creates one binary variable and one closed-neighborhood constraint per vertex, matching the same semantics and accepting the empty graph.
• The model implementation in src/models/graph/minimum_dominating_set.rs defines domination using self-plus-neighbors and supports signed i32 weights.

Well-written

• Source, Target, Motivation, Reference, Reduction Algorithm, Size Overhead, Validation Method, Example, and BibTeX sections are all present and substantive.
• n, G=(V,E), w_v, and each constructed D_v are defined before use.
• The overhead names universe_size and num_sets exactly match the target's registered size_fields; both formulas use the valid source getter num_vertices.
• The extraction rule is explicit and one-to-one.
• The five-vertex weighted path is small enough to brute-force and has multiple feasible solutions with different values, so it can detect feasibility, extraction, and objective-preservation errors.

Recommendations

• Add one sentence to the algorithm or validation section: “Self-loops and repeated edges, which SimpleGraph can represent, do not change the construction because each N[v] is treated as a set.”
• If stronger bibliographic attribution is desired, cite a source that explicitly states the reduction (for example, the UMass proof above) in addition to Garey–Johnson's problem definitions.

[isPANN]

Rule Fix

Diagnosis:

• Checks 1–10 and 12 passed: the direction, iff proof, coordinate-wise extraction, polynomial construction, overhead, example, value type, and signed objective preservation are correct; the set-system target has no undirected rerouting risk.
• Check 11 was under-documented: SimpleGraph permits self-loops and repeated edges, but the issue did not state why these inputs still produce a valid target instance.

Literature:

• The UMass COMPSCI 311 solution for Problem 8(a) gives the canonical construction U=V and one closed-neighborhood set S_v={v}∪N(v) per vertex, with explicit forward and backward proofs. The issue matches that construction exactly.
• Garey–Johnson supports the cited problem definitions; the weighted i32 extension follows by copying each vertex weight to its corresponding set.

Changes:

• Added the missing statement that self-loops and repeated edges do not affect the reduction because each closed neighborhood is treated as a set.
• Left the mathematically correct construction, overhead formulas, extraction, and worked example unchanged.

Smoke test:

• 110 checks passed across the required YES, NO-bound, boundary, objective-agreement, extraction, overhead, and target-validity buckets.
• Confirmed the five-vertex weighted path, empty graph, negative isolated vertex, self-loop/parallel-edge input, 100 deterministic signed-weight instances, and five overhead spot-checks.

[isPANN]

Issue Quality Check — Rule (Re-check)

Previously: 4 passes, 1 warning. Now: 5 passes, 0 warnings after documenting legal self-loop and repeated-edge inputs.

Check	Result	Details
Usefulness	✅ Pass	Both exact variants resolve, and pred path MinimumDominatingSet MinimumSetCovering --json still reports no existing path.
Non-trivial	✅ Pass	The rule transforms a graph into a set system by constructing one closed-neighborhood set per vertex; this is not an identity, subtype cast, or relabeling.
Correctness	✅ Pass	The cited Garey–Johnson book and definitions are real; the UMass COMPSCI 311 solution independently gives the same U=V, S_v={v}∪N(v) construction and both proof directions. Copying signed i32 weights preserves the objective coordinate-wise.
Well-written	✅ Pass	All required sections are complete, metric names match the target schema, extraction is explicit, and the weighted path example has multiple feasible solutions with different values.
Completeness	✅ Pass	The literature construction handles arbitrary graphs. The edited body now explicitly covers empty graphs, isolated vertices, self-loops, and repeated edges; neighborhood deduplication makes every constructed set valid.

Verification details

• The source value is Min<i32> and the target value is Min<i32>, so the objective types are compatible.
• The overhead is exact for this construction: universe_size = num_vertices and num_sets = num_vertices.
• Code inspection confirms MinimumDominatingSet::closed_neighborhood collects neighbors into a HashSet, while MinimumSetCovering accepts the resulting subsets and signed weights.
• Corner-case traces passed for the empty graph, a negative-weight isolated vertex, and an input containing a self-loop and repeated edge.
• An independent smoke test passed 110 checks: the worked YES example, a NO bound, three boundary cases, 100 signed-weight objective/extraction/validity cases, and five overhead spot-checks.

Overall: 5 passed, 0 failed, 0 warnings.