[Rule] VERTEX COVER to MINIMUM CUT INTO BOUNDED SETS

[isPANN]

---

name: Rule
about: Propose a new reduction rule
title: "[Rule] VERTEX COVER to MINIMUM CUT INTO BOUNDED SETS"
labels: rule
assignees: ''
canonical_source_name: 'VERTEX COVER'
canonical_target_name: 'MINIMUM CUT INTO BOUNDED SETS'
source_in_codebase: true
target_in_codebase: false

Source: VERTEX COVER
Target: MINIMUM CUT INTO BOUNDED SETS
Motivation: Establishes NP-completeness of MINIMUM CUT INTO BOUNDED SETS via polynomial-time reduction from VERTEX COVER. While the standard minimum s-t cut problem is polynomial-time solvable via network flow, adding a balance constraint on partition sizes makes the problem NP-complete. This result, due to Garey, Johnson, and Stockmeyer (1976), demonstrates that even the restriction to unit weights and equal-sized partitions (minimum bisection) remains NP-complete.

Reference: Garey & Johnson, Computers and Intractability, ND17, p.210

GJ Source Entry

[ND17] MINIMUM CUT INTO BOUNDED SETS
INSTANCE: Graph G=(V,E), positive integers K and J.
QUESTION: Can V be partitioned into J disjoint sets V_1,...,V_J such that each |V_i|<=K and the number of edges with endpoints in different parts is minimized, i.e., such that the number of such edges is no more than some bound B?
Reference: [Garey and Johnson, 1979]. Transformation from VERTEX COVER.
Comment: NP-complete even for J=2.

Reduction Algorithm

Summary:
Given a MinimumVertexCover instance (G = (V, E), k) where G is an undirected graph with n = |V| vertices and m = |E| edges, construct a MinimumCutIntoBoundedSets instance (G', s, t, B, K) as follows:

1. Graph construction: Start with the original graph G = (V, E). Add two special vertices s and t (the source and sink). Connect s to every vertex in V with an edge, and connect t to every vertex in V with an edge.

2. Weight assignment: Assign weight 1 to all edges in E (original graph edges). Assign large weight M = m + 1 to all edges incident to s and t. This ensures that in any optimal cut, no edges between s/t and V are cut (they are too expensive).

   Alternatively, a simpler construction for the unit-weight, J=2 case:

   • Create a new graph G' from G by adding n - 2k isolated vertices (padding vertices) to make the total vertex count N = 2n - 2k (so each side of a balanced partition has exactly n - k vertices).
   • Choose s as any vertex in V and t as any other vertex in V (or as newly added vertices).
   • Set B = n - k (each partition side has at most n - k vertices) and cut bound K' related to k.

3. Key encoding idea: A minimum vertex cover of size k in G corresponds to a balanced partition where the k cover vertices are on one side and the n - k non-cover vertices are on the other side. The number of cut edges equals the number of edges with at least one endpoint in the cover, which relates to the vertex cover structure. The balance constraint prevents trivially putting all vertices on one side.

4. Size bound parameter: B = ceil(|V'|/2) for the bisection variant.

5. Cut bound parameter: The cut weight is set to correspond to the number of edges incident to the vertex cover.

6. Solution extraction: Given a balanced partition (V1, V2) with cut weight <= K', the side containing s has the non-cover vertices, and the other side has the cover vertices (or vice versa). The vertex cover is read from the partition.

Note: The GJ entry states the transformation is from VERTEX COVER. The original proof by Garey, Johnson, and Stockmeyer (1976) in "Some Simplified NP-Complete Graph Problems" actually shows NP-completeness of the related SIMPLE MAX CUT problem first, then transforms to MINIMUM CUT INTO BOUNDED SETS. The exact intermediate chain may be: VERTEX COVER -> SIMPLE MAX CUT -> MINIMUM CUT INTO BOUNDED SETS. The key difficulty is the balance constraint B on partition sizes.

Size Overhead

Symbols:

• n = num_vertices of source MinimumVertexCover instance (|V|)
• m = num_edges of source MinimumVertexCover instance (|E|)
• k = cover size bound parameter

Target metric (code name)	Polynomial (using symbols above)
num_vertices	num_vertices + 2
num_edges	num_edges + 2 * num_vertices

Derivation (with s,t construction):

• Vertices: original n vertices plus s and t = n + 2
• Edges: original m edges plus n edges from s to each vertex plus n edges from t to each vertex = m + 2n

Validation Method

• Closed-loop test: reduce a MinimumVertexCover instance to MinimumCutIntoBoundedSets, solve target with BruteForce (enumerate all partitions with s in V1 and t in V2, check size bounds, compute cut weight), extract vertex cover from partition, verify it covers all edges
• Test with a graph with known minimum vertex cover (e.g., star graph K_{1,n-1} has minimum VC of size 1)
• Test with both feasible and infeasible VC bounds to verify bidirectional correctness
• Verify vertex and edge counts match the overhead formulas

Example

Source instance (MinimumVertexCover):
Graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 7 edges:

• Edges: {0,1}, {0,2}, {1,2}, {1,3}, {2,4}, {3,4}, {4,5}
• n = 6, m = 7
• Minimum vertex cover: size k = 3, e.g., {1, 2, 4} covers all edges:
  • {0,1}: 1 in cover. {0,2}: 2 in cover. {1,2}: both. {1,3}: 1 in cover.
  • {2,4}: both. {3,4}: 4 in cover. {4,5}: 4 in cover.

Constructed target instance (MinimumCutIntoBoundedSets):

Graph G' with 8 vertices {0, 1, 2, 3, 4, 5, s, t} and 7 + 12 = 19 edges:

• Original edges: {0,1}, {0,2}, {1,2}, {1,3}, {2,4}, {3,4}, {4,5} (weight 1 each)
• s-edges: {s,0}, {s,1}, {s,2}, {s,3}, {s,4}, {s,5} (weight M = 8 each)
• t-edges: {t,0}, {t,1}, {t,2}, {t,3}, {t,4}, {t,5} (weight M = 8 each)

Parameters: B = 7 (each side at most 7 vertices), s in V1, t in V2.

Solution mapping:

• Any optimal partition avoids cutting the heavy s-edges and t-edges.
• Partition: V1 = {s, 0, 3, 5} (vertices not in cover plus s), V2 = {t, 1, 2, 4} (cover vertices plus t)
• Cut edges (weight 1 each): {0,1}, {0,2}, {1,3}, {3,4}, {4,5} = 5 cut edges
• |V1| = 4 <= B, |V2| = 4 <= B
• Extracted vertex cover: vertices on t's side = {1, 2, 4}
• Verification: all 7 original edges have at least one endpoint in {1, 2, 4}

References

• [Garey and Johnson, 1979]: [Garey19xx] M. R. Garey and D. S. Johnson (1979). "Unpublished results".
• [Garey, Johnson, and Stockmeyer, 1976]: [GareyJohnsonStockmeyer1976] M. R. Garey, D. S. Johnson, and L. Stockmeyer (1976). "Some Simplified NP-Complete Graph Problems." Theoretical Computer Science, 1(3):237-267.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	⚠️ Warn	Target problem "MinimumCutIntoBoundedSets" not in codebase; novel direction but requires new model first
Non-trivial	⚠️ Warn	Construction involves gadgets (s/t vertices, weighted edges), but algorithm is too vague to confirm non-triviality
Correctness	❌ Fail	Reduction chain is misattributed; algorithm presents two contradictory constructions; reference entry is malformed
Well-written	❌ Fail	Algorithm is a hand-wave with two incompatible sketches; symbols inconsistent; overhead unverifiable

Overall: 0 passed, 2 warnings, 2 failed

---

Usefulness

The target problem "MINIMUM CUT INTO BOUNDED SETS" (GJ ND17) does not exist in the codebase. There is no existing path from MinimumVertexCover to any such problem, so this reduction would be novel if the target model is added first. However, since the target is not yet implemented, this rule cannot be implemented until a corresponding [Model] issue is filed and merged.

Verdict: Warn — useful in principle, but requires a prerequisite model issue.

Non-trivial

The proposed construction involves adding source/sink vertices with heavy-weight edges, which is a legitimate gadget-based approach. However, the algorithm section presents two different, incompatible constructions (one with weighted s/t edges, one with padding vertices for bisection), making it impossible to determine which construction is actually being proposed and whether either is genuinely non-trivial.

Verdict: Warn — potentially non-trivial, but the algorithm must be disambiguated to confirm.

Correctness

Several correctness problems were identified:

3a: Reduction chain is misattributed. The issue states the GJ entry says "Transformation from VERTEX COVER." However, the actual reduction chain in Garey, Johnson, and Stockmeyer (1976) goes through Simple Max Cut first. The paper "Some Simplified NP-Complete Graph Problems" proves Simple Max Cut NP-complete, and Minimum Cut Into Bounded Sets (including the minimum bisection special case J=2) is shown NP-complete via Simple Max Cut, not directly from Vertex Cover. The standard chain is: Max Cut -> Max Bisection -> Minimum Bisection (via complement graph). The issue's Note section even acknowledges this uncertainty ("The exact intermediate chain may be: VERTEX COVER -> SIMPLE MAX CUT -> MINIMUM CUT INTO BOUNDED SETS"), which contradicts its own claimed direct reduction.

3b: Reference entry is malformed. The first reference is listed as:

[Garey19xx] M. R. Garey and D. S. Johnson (1979). "Unpublished results."

This is clearly a placeholder/error. Garey & Johnson (1979) is the published book "Computers and Intractability", not "Unpublished results." The BibTeX key uses "19xx" which is also malformed.

3c: The paper reference is verified. Garey, Johnson, and Stockmeyer (1976), "Some Simplified NP-Complete Graph Problems," Theoretical Computer Science, 1(3):237-267 — this paper exists and is correctly cited with correct authors, year, journal, volume, and pages.

3d: Algorithm correctness is unverifiable. Because two contradictory constructions are presented (weighted s/t construction vs. padding-vertices bisection construction), and neither is worked through rigorously, we cannot verify that the reduction preserves solutions correctly.

Verdict: Fail — the direct reduction from Vertex Cover is not established in the literature as claimed; the known chain goes through Simple Max Cut. The reference entry is malformed.

Well-written

4a: Information Completeness — several issues:

• The Reduction Algorithm section presents two alternative constructions ("Alternatively, a simpler construction...") without committing to one. A reduction rule must specify exactly one procedure.
• Steps 4, 5, and 6 are vague placeholders ("B = ceil(|V'|/2) for the bisection variant", "The cut weight is set to correspond to the number of edges incident to the vertex cover").

4b: Algorithm Completeness — Fail.
The algorithm is a high-level sketch, not an implementable procedure:

• Step 3 says "relates to the vertex cover structure" without defining the exact relationship.
• Step 5 says "The cut weight is set to correspond to..." without giving a formula.
• Step 6 says "the side containing s has the non-cover vertices... (or vice versa)" — the ambiguity "(or vice versa)" means the solution extraction is undefined.
• The Note at the end admits the reduction chain may be indirect, undermining the entire construction.

4c: Symbol and Notation Consistency — issues:

• The algorithm defines M = m + 1 but the overhead table does not account for edge weights (the target problem as defined in GJ has unweighted edges and a cut bound B).
• The overhead table uses num_vertices and num_edges but the target problem "MinimumCutIntoBoundedSets" does not exist, so there are no size_fields to validate against.
• Symbol K appears in the constructed instance parameters but is overloaded (used for both the vertex cover size bound and the cut bound K').

4d: Example Quality — partial pass.
The example is reasonably detailed and walks through vertex/edge counts and solution mapping. However, the parameter B=7 is stated without derivation, and the example follows the weighted s/t construction while the issue also proposes an alternative padding construction — it is unclear which algorithm variant the example demonstrates.

Verdict: Fail — the algorithm is not implementable as written; two incompatible constructions are mixed; key steps are hand-waves.

Recommendations

1. Choose one construction and fully specify it. The weighted s/t approach or the padding-vertices bisection approach — not both.
2. Clarify the reduction chain. The known literature chain is Max Cut -> Minimum Bisection. A direct reduction from Vertex Cover may exist but needs to be explicitly constructed and proven correct, not just asserted.
3. Fix the malformed reference. Replace [Garey19xx] "Unpublished results" with the correct citation: Garey & Johnson (1979), "Computers and Intractability: A Guide to the Theory of NP-Completeness", W. H. Freeman.
4. File a [Model] issue first. The target problem needs to be defined and implemented before this rule can be added.
5. Provide complete solution extraction. Step 6 must unambiguously specify how to read the vertex cover from the partition, without "or vice versa."

[isPANN]

Issue Quality Check — Rule (Re-check)

Check	Result	Details
Usefulness	✅ Pass	No existing path; both models now in codebase
Non-trivial	✅ Pass	Construction involves gadget vertices and weighted edges
Correctness	❌ Fail	Reduction algorithm is fundamentally incorrect; reference malformed
Well-written	❌ Fail	Two contradictory constructions; example factually wrong; hand-wave steps

Overall: 2 passed, 0 warnings, 2 failed

Changes from previous check (2026-03-11): Usefulness upgraded from Warn to Pass (target model MinimumCutIntoBoundedSets now exists in codebase). Non-trivial upgraded from Warn to Pass (gadget construction confirmed). Correctness and Well-written remain Failed with additional evidence from programmatic validation.

---

Usefulness

Pass. No reduction path exists from MinimumVertexCover to MinimumCutIntoBoundedSets. Both problems now exist in the codebase (the target model was added since the previous check). This would be a novel reduction connecting these two problems.

The motivation is substantive — it explains why adding a balance constraint to minimum cut makes the problem NP-complete, citing the Garey-Johnson-Stockmeyer (1976) result.

Non-trivial

Pass. The proposed construction involves adding source/sink gadget vertices with heavy-weight edges, which is a genuine structural transformation (not a relabeling or subtype coercion).

Correctness

Fail. Multiple correctness issues identified:

3a: The reduction algorithm is fundamentally incorrect. Python brute-force validation reveals the core flaw: in the proposed s-t construction, every partition of the original vertices cuts exactly n heavy edges (each original vertex connects to both s and t, so exactly one heavy edge per vertex is always cut). The heavy edge contribution is a constant n × M = 48 across all partitions, making the heavy weights irrelevant to the optimization. The bound B = 7 (= n+1) permits degenerate partitions where all original vertices sit on one side, yielding 0 original-edge cuts and total weight 48 — which is optimal. The vertex cover structure is not encoded.

3b: Malformed reference. The first reference is listed as [Garey19xx] "Unpublished results" — this is a placeholder error. The correct citation is: Garey & Johnson (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman. BibTeX key in project bibliography: garey1979.

3c: Reduction chain is misattributed. The GJ book lists ND17 as "Transformation from VERTEX COVER," but the known proof chain in the literature goes through Max Cut: Max Cut → Max Bisection (add isolated vertices) → Min Bisection (complement graph). The issue's Note section even acknowledges this uncertainty. A direct reduction from Vertex Cover may exist but is not established in the cited references and would need to be independently proven correct.

3d: GJS 1976 paper is correctly cited. Garey, Johnson, and Stockmeyer (1976), "Some Simplified NP-Complete Graph Problems," Theoretical Computer Science, 1(3):237-267 — verified as existing with correct metadata. BibTeX key in project bibliography: gareyJohnsonStockmeyer1976.

Well-written

Fail. Multiple issues:

4a: Two contradictory constructions. The algorithm presents a weighted s-t construction (Step 1-2) and then "Alternatively, a simpler construction for the unit-weight, J=2 case" with padding vertices. A reduction must specify exactly one procedure.

4b: Algorithm is not implementable. Steps 3-6 are hand-waves:

• Step 3: "relates to the vertex cover structure" — no formula given
• Step 5: "The cut weight is set to correspond to..." — undefined
• Step 6: "the side containing s has the non-cover vertices... (or vice versa)" — ambiguous solution extraction

4c: Symbol overloading. K is used for both the vertex cover size bound and the cut bound K'. The overhead table uses num_vertices and num_edges but the target problem reports size_fields: [], so overhead formulas cannot be validated against code getters.

4d: Example is factually wrong. Python brute-force validation found:

• The issue claims the partition V1={s,0,3,5}, V2={t,1,2,4} has cut weight 5 (only counting weight-1 edges). Actual total cut weight is 53 (5 original edges + 6 heavy edges × weight 8 = 48).
• The brute-force optimal cut weight is 48 (all original vertices on one side), not 53.
• The issue's partition is suboptimal, not optimal.
• Round-trip fails: the optimal target partitions are trivial (all vertices on one side) and do not extract a meaningful vertex cover.
• Stats: 6 source vertices, 7 source edges, minimum vertex cover size 3, 2 optimal covers ({0,1,4} and {1,2,4}), target has 8 vertices and 19 edges (overhead formulas n+2 and m+2n are numerically correct for graph size).

Recommendations

1. The reduction algorithm needs to be completely redesigned. The s-t construction with heavy edges does not encode vertex cover structure because heavy edge costs are constant across all partitions. Consider using the known chain: Max Cut → Max Bisection → Min Bisection.
2. Choose one construction and fully specify it with complete, numbered, implementable steps.
3. Fix the malformed reference. Replace [Garey19xx] "Unpublished results" with garey1979 — Garey & Johnson (1979), Computers and Intractability.
4. Provide a correct, fully worked example that demonstrates the round-trip property.
5. Clarify the reduction chain. If proposing a direct Vertex Cover → Min Cut Into Bounded Sets reduction, it must be independently proven correct — the standard literature uses Max Cut as an intermediate step.