[Rule] VERTEX COVER to COMPARATIVE CONTAINMENT

[isPANN]

Source: VERTEX COVER
Target: COMPARATIVE CONTAINMENT
Motivation: Establishes NP-completeness of COMPARATIVE CONTAINMENT via polynomial-time reduction from VERTEX COVER. The reduction, due to Plaisted (1976), encodes the vertex cover structure into weighted set containment: each vertex becomes an element of the universe, and edge-coverage constraints are translated into two collections of weighted subsets (R and S) such that a vertex cover of bounded size exists if and only if a subset Y of the universe achieves at least as much R-containment weight as S-containment weight.
Reference: Garey & Johnson, Computers and Intractability, SP10, p.223

GJ Source Entry

[SP10] COMPARATIVE CONTAINMENT
INSTANCE: Two collections R={R_1,R_2,...,R_k} and S={S_1,S_2,...,S_l} of subsets of a finite set X, weights w(R_i) in Z^+, 1<=i<=k, and w(S_j) in Z^+, 1<=j<=l.
QUESTION: Is there a subset Y <= X such that
Sum_{Y <= R_i} w(R_i) >= Sum_{Y <= S_j} w(S_j) ?
Reference: [Plaisted, 1976]. Transformation from VERTEX COVER.
Comment: Remains NP-complete even if all subsets in R and S have weight 1 [Garey and Johnson, ----].

Reduction Algorithm

Summary:

Given a VERTEX COVER instance (graph G = (V, E), bound K), construct a COMPARATIVE CONTAINMENT instance as follows. Let n = |V| and m = |E|.

1. Universe: Let X = V (one element per vertex).
2. Collection R (reward sets): For each vertex v in V, create a set R_v = V \ {v} with weight w(R_v) = 1. This rewards Y for each vertex it does NOT include: Y subset of R_v iff v not in Y. Thus the total R-weight equals n - |Y|.
3. Collection S (penalty sets): Two kinds:
   • For each edge e = {u, v} in E, create S_e = V \ {u, v} with weight w(S_e) = n + 1. Then Y subset of S_e iff neither u nor v is in Y, i.e., edge e is uncovered. Each uncovered edge contributes a large penalty.
   • One budget set S_0 = V with weight w(S_0) = n - K. Since Y subset of V always holds, this contributes a constant penalty of n - K.
4. Correctness: The containment inequality becomes:
   (n - |Y|) >= (n + 1) * (number of uncovered edges) + (n - K)
   which simplifies to:
   K - |Y| >= (n + 1) * (number of uncovered edges).
   • If Y is a vertex cover with |Y| <= K: the right side is 0 and K - |Y| >= 0. Satisfied.
   • If Y is a vertex cover with |Y| > K: the right side is 0 but K - |Y| < 0. Not satisfied.
   • If Y is not a vertex cover: at least one edge is uncovered, so the right side is >= n + 1 > n >= K - |Y|. Not satisfied.
     Hence the inequality holds if and only if Y is a vertex cover of size at most K.
5. Solution extraction: The witness Y from the COMPARATIVE CONTAINMENT instance is directly the vertex cover.

Size Overhead

Symbols:

• n = |V| = num_vertices of source graph
• m = |E| = num_edges of source graph

Target metric (code name)	Polynomial (using symbols above)
universe_size	num_vertices (= n)
num_r_sets	num_vertices (= n)
num_s_sets	num_edges + 1 (= m + 1)

Derivation: The universe X has one element per vertex. Collection R has one set per vertex. Collection S has one set per edge plus one budget set. Total construction is O(n^2 + mn) accounting for set contents.

Validation Method

• Closed-loop test: reduce source VERTEX COVER instance, solve target COMPARATIVE CONTAINMENT with BruteForce, extract solution, verify on source
• Compare with known results from literature
• Test with small graphs (triangle, path, cycle) where vertex cover is known

Example

Source instance (VERTEX COVER):
Graph G with 6 vertices V = {v_0, v_1, v_2, v_3, v_4, v_5} and 7 edges:
E = { {v_0,v_1}, {v_0,v_2}, {v_1,v_2}, {v_1,v_3}, {v_2,v_4}, {v_3,v_4}, {v_4,v_5} }
Bound K = 3.
(A minimum vertex cover is {v_1, v_2, v_4} of size 3.)

Constructed COMPARATIVE CONTAINMENT instance:
Universe X = {v_0, v_1, v_2, v_3, v_4, v_5}, n = 6, m = 7.

Collection R (one set per vertex, weight 1 each):

• R_0 = {1, 2, 3, 4, 5}, w = 1
• R_1 = {0, 2, 3, 4, 5}, w = 1
• R_2 = {0, 1, 3, 4, 5}, w = 1
• R_3 = {0, 1, 2, 4, 5}, w = 1
• R_4 = {0, 1, 2, 3, 5}, w = 1
• R_5 = {0, 1, 2, 3, 4}, w = 1

Collection S (one set per edge with weight n + 1 = 7, plus one budget set):

• S_{0,1} = {2, 3, 4, 5}, w = 7
• S_{0,2} = {1, 3, 4, 5}, w = 7
• S_{1,2} = {0, 3, 4, 5}, w = 7
• S_{1,3} = {0, 2, 4, 5}, w = 7
• S_{2,4} = {0, 1, 3, 5}, w = 7
• S_{3,4} = {0, 1, 2, 5}, w = 7
• S_{4,5} = {0, 1, 2, 3}, w = 7
• S_budget = {0, 1, 2, 3, 4, 5}, w = n - K = 3

Solution:
Choose Y = {v_1, v_2, v_4}.

R-containment: Y is a subset of R_v iff v is not in Y. Vertices not in Y: {v_0, v_3, v_5}. So Y is contained in R_0, R_3, and R_5. R-weight = 3 (= n - |Y| = 6 - 3).

S-containment (edges): Y is a subset of S_e = V \ {u,v} iff neither u nor v is in Y. Since Y = {1,2,4} is a vertex cover, every edge has at least one endpoint in Y, so Y is NOT contained in any S_e. Edge S-weight = 0.

S-containment (budget): Y is a subset of V, so S_budget always contributes. Budget S-weight = 3.

Total S-weight = 0 + 3 = 3.

Comparison: R-weight (3) >= S-weight (3)? YES (tight equality).

This confirms the vertex cover {v_1, v_2, v_4} of size 3 maps to a feasible COMPARATIVE CONTAINMENT solution.

Negative example: Y = {v_1, v_3} (size 2, but NOT a vertex cover — edges {0,2}, {2,4}, {4,5} are uncovered).
R-weight = 6 - 2 = 4.
S-edge-weight: {0,2}: 0 not in Y, 2 not in Y — uncovered, contributes 7. {2,4}: uncovered, contributes 7. {4,5}: uncovered, contributes 7. Total edge penalty = 21.
S-budget = 3. Total S-weight = 24.
Condition: 4 >= 24? NO. Correctly rejected.

References

• [Plaisted, 1976]: [Plaisted1976] D. Plaisted (1976). "Some polynomial and integer divisibility problems are {NP}-hard". In: Proceedings of the 17th Annual Symposium on Foundations of Computer Science, pp. 264-267. IEEE Computer Society.
• [Garey and Johnson, ----]: (not found in bibliography)

[isPANN]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	Pass	No existing reduction path DecisionMinimumVertexCover -> ComparativeContainment (verified via pred path). Novel edge.
Non-trivial	Pass	Gadget construction with two weighted set families and explicit budget set; not a relabeling or coercion.
Correctness	Pass	Plaisted 1976 (STAN-CS-76-583) is in docs/paper/references.bib and Garey & Johnson SP10 (p.223) confirms the reduction direction (VERTEX COVER -> COMPARATIVE CONTAINMENT). Example arithmetic verified by hand.
Completeness	Warn	Algorithm is silent on two real corner cases (see Completeness section).
Well-written	Warn	Algorithm and example are clear, but the overhead table references universe_size/num_r_sets/num_s_sets while pred show ComparativeContainment --json reports size_fields: [] — implementer must add size_fields (or size_getters in the rule registration) for the overhead expressions to compile.

Overall: 3 passed, 0 failed, 2 warnings

---

Usefulness

• pred path DecisionMinimumVertexCover ComparativeContainment returns "No reduction path". Same for pred path MinimumVertexCover ComparativeContainment.
• pred show ComparativeContainment --json confirms reduces_from: []. This rule introduces the first incoming edge to ComparativeContainment, removing it from the orphan set.
• Motivation is concrete: NP-completeness witness for ComparativeContainment via a textbook Plaisted construction. Pass.

Non-trivial

The construction builds two distinct weighted set families plus a calibrated budget set whose weight n - K is what couples the cardinality bound K of vertex cover to the comparative inequality. This is a genuine gadget (uncovered edges contribute a (n+1)-weight penalty large enough to dominate the n - |Y| reward), not a substitution.

Correctness

• Reference [Plaisted1976] is already in docs/paper/references.bib as @techreport{plaisted1976, ...} with matching title "Some Polynomial and Integer Divisibility Problems Are NP-Hard" and number STAN-CS-76-583. Confirmed via web search that the paper exists and that Garey & Johnson SP10 cites it as the transformation source from VERTEX COVER (the conference version is at FOCS 1976, the technical report is the long version).
• The algorithm's algebraic argument is reproduced step by step and verified:
  • R-weight = n - |Y| (one unit per vertex outside Y).
  • S-weight = (n+1) * (uncovered edges) + (n - K).
  • Equivalence R-weight >= S-weight <=> Y is a vertex cover of size <= K holds because (n+1) > K - |Y| whenever any edge is uncovered, so a non-cover always fails; a cover satisfies the inequality iff |Y| <= K.
• Worked example checks out: minimum vertex cover of the 6-vertex 7-edge graph is {v_1, v_2, v_4} of size 3 (I re-verified that K=2 is infeasible). The negative case Y = {v_1, v_3} with three uncovered edges gives R=4, S=21+3=24, correctly rejected.

Completeness

Literature: G&J SP10 states the reduction is from the unrestricted VERTEX COVER decision problem (unit-weight, bound K). The Plaisted construction in the issue matches the standard reference proof and works "for any instance" in the literature sense — there is no precondition on the graph itself.

Two corner cases I traced by hand against the issue's algorithm reveal silent assumptions that the issue body does not state:

1. K = n (or more generally K >= n): The budget set is S_0 = V with weight w(S_0) = n - K. The ComparativeContainment model enforces validate_weight_family with strict positivity (weight > 0, see src/models/set/comparative_containment.rs:212-220). When K = n the construction tries to register a weight-0 set and crashes. This is a vacuous YES case for the source (selecting all vertices trivially covers every edge), so the standard fix is a one-line preprocessing: if K >= n, emit a canonical YES ComparativeContainment instance directly. The issue should state this assumption or the preprocessing step.

2. Weighted source instances: The codebase only registers Decision<MinimumVertexCover<SimpleGraph, i32>> (weighted vertex cover) — pred show DecisionMinimumVertexCover --json shows the i32-weighted variant only. The issue's algorithm uses |Y| (cardinality) and K (an integer bound on cardinality), so it implicitly restricts to unit weights. This precedent already exists in src/rules/decisionminimumvertexcover_hamiltoniancircuit.rs:301-305, which asserts weights.iter().all(|&weight| weight == 1) with comment "Garey-Johnson Theorem 3.4 requires unit vertex weights". The issue should either mirror this assertion or generalize the construction to weighted vertex cover (replacing n - |Y|, K, and n with weighted analogues).

Other corner cases traced cleanly:

• Empty edge set with K = 0, n = 1: R_0 = ∅ (weight 1), S_0 = {v_0} (weight 1). Y = ∅ gives R=1, S=1, inequality holds. Correct (trivial cover).
• Single-edge graph with K = 0, n = 2: Every Y fails the inequality (R=2 vs S=5 at best). Correct (no size-0 cover exists for a non-empty edge set).
• Isolated-vertex graph with K = 0: handled correctly (no edge penalties, R=S=n).

Verdict: Warn (algorithm correct on every traced corner case under the standard unit-weight / K < n assumptions, but the issue body does not document either assumption). Both are easy to address with a sentence in the algorithm preamble plus a one-line preprocessing step.

Well-written

• All template sections are present and substantive.
• Algorithm is step-by-step and implementable; solution extraction (Y -> vertex cover) is explicit.
• Symbols n, m, K, Y, R_v, S_e, S_0 are all defined before use.
• Example is non-trivial (6 vertices, 7 edges, multiple feasible covers of differing sizes), shows the source instance, the constructed target, and both positive and negative test configurations — strong round-trip material.

Items to fix before implementation:

• Schema mismatch on size_fields: pred show ComparativeContainment --json returns size_fields: [] — the model's ProblemSchemaEntry does not yet declare universe_size, num_r_sets, num_s_sets as size fields. The issue's overhead table uses these names; the implementer will either need to extend the schema or supply explicit size_getters in the rule registration. Worth flagging in the issue so the implementation PR doesn't get blocked.
• Add the K-versus-n precondition and the unit-weight assumption to the "Reduction Algorithm" section (one extra line at the start: "Assume 0 <= K < n and all vertex weights equal 1; otherwise emit a canonical YES instance directly.").

Recommendations

• When implementing, mirror the unit-weight assertion pattern from src/rules/decisionminimumvertexcover_hamiltoniancircuit.rs:301-305 so the rule fails fast on weighted inputs instead of silently producing a wrong answer.
• The ComparativeContainment model could benefit from extending its ProblemSchemaEntry to declare universe_size, num_r_sets, num_s_sets as size_fields so future incoming reductions can reference them in overhead expressions without per-rule size_getters.

[isPANN]

auto-pipeline: implementation landed on batch-add-models as commit 87e47e5.

[isPANN]

/review-structural — commit 87e47e5 (post-impl, code-quality + bug sweep)

Verdict: pass — Plaisted 1976 construction matches the issue, overhead is consistent with the asymptotic upper bound, corner cases are sound, and the rule is fully wired (paper, example-db, mod.rs).

Issue compliance

• Overhead matches issue: yes — universe_size = num_vertices, num_r_sets = num_vertices, num_s_sets = num_edges + 1 match the issue's overhead table verbatim.
• Algorithm matches issue: yes — non-trivial branch builds R_v = V \ {v} (weight 1) for each vertex, S_e = V \ {u, v} (weight n + 1) for each edge, and one budget set S_0 = V (weight n - K). Construction in reduce_to() lines up with the issue's "Reduction Algorithm" step-by-step. Source-side assert! requiring unit weights is consistent with the issue framing (Plaisted's reduction is specified for unit-weight VC).
• Canonical example: ok — decisionminimumvertexcover_to_comparativecontainment builds P4 with K=2 (the issue picks a 6-vertex graph, but smaller P4 is more pedagogical for the paper and keeps the brute-force witness search cheap). Example registered in src/rules/mod.rs:505 and loaded by docs/paper/reductions.typ:11850.

Findings

• Blockers (correctness): none
  • Non-trivial branch: hand-traced inequality K - |Y| >= (n + 1) · (#uncovered) matches the construction (R-weight = n - |Y| since Y ⊆ R_v iff v ∉ Y; edge S-weight (n + 1)·(#uncovered); budget S-weight n - K).
  • Trivial-YES branch (K >= n): emits universe size 0 with no sets. evaluate(&[]) returns Or(true) (both R and S sums are 0, 0 >= 0). extract_solution returns the all-ones source config, which is always a valid cover with |Y| = n <= K. Sound.
  • Trivial-NO branch (K < 0): emits universe size 1, no R sets, single S set {0} with weight 1. For any config, R-weight = 0, S-weight = 1 (Y ⊆ {0} always since universe is {0}), so 0 >= 1 is false → unsatisfiable. Sound.
  • Overhead vs construction: corner cases produce smaller targets (0 or 1 universe element) than the polynomial bound predicts, which is fine since overhead is documented as an asymptotic upper bound.
  • complement_singleton and complement_pair correctly skip the excluded vertex/edge endpoints; both are O(n).
• Nits (quality/HCI): none material
  • Negative-bound branch leaves trivial_yes = None, so extract_solution would return an all-zero cover if a target witness were somehow found. In practice the target is unsatisfiable so this codepath is unreachable, but a trivial_no: Option<Vec<usize>> symmetric to trivial_yes (returning an invalid source config explicitly) could make intent clearer. Not a blocker — the current logic is correct.
  • edge_weight = i32::try_from(n + 1) and budget_weight = i32::try_from(n - k) use expect for what is effectively an integer fit check. For graphs with n beyond i32::MAX - 1 this would panic at construction; acceptable given other models in the repo apply the same assumption.
  • Test coverage is strong: 8 tests covering structure counts, closed-loop YES/NO, witness extraction, both trivial-YES branches (K = n and K > n), trivial-NO branch, and the unit-weight #[should_panic] guard.