[Model] MinimumCutIntoBoundedSets

[isPANN]

Motivation

MINIMUM CUT INTO BOUNDED SETS from Garey & Johnson, A2 ND17. An NP-complete graph partitioning problem that combines the classical minimum s-t cut problem with a balance constraint on the sizes of the resulting partition sets. While minimum s-t cut without balance constraints is polynomial-time solvable via network flow, adding the requirement that both sides of the partition have bounded size makes the problem NP-complete. This problem is fundamental to VLSI layout, load balancing, and graph bisection applications.

Associated rules:

• SIMPLE MAX CUT -> MINIMUM CUT INTO BOUNDED SETS (ND17) — per G&J, "Transformation from SIMPLE MAX CUT."

Definition

Name: MinimumCutIntoBoundedSets
Canonical name: Minimum Cut Into Bounded Sets (also: Balanced s-t Cut, Bounded Bisection)
Reference: Garey & Johnson, Computers and Intractability, A2 ND17

Mathematical definition:

INSTANCE: Graph G = (V,E), weight w(e) in Z+ for each e in E, specified vertices s,t in V, positive integer B <= |V|, positive integer K.
QUESTION: Is there a partition of V into disjoint sets V1 and V2 such that s in V1, t in V2, |V1| <= B, |V2| <= B, and such that the sum of the weights of the edges from E that have one endpoint in V1 and one endpoint in V2 is no more than K?

Variables

• Count: n = |V| binary variables (one per vertex)
• Per-variable domain: binary {0, 1} — side of the partition (0 = V1, 1 = V2)
• dims() implementation: vec![2; self.graph.num_vertices()]
• Meaning: variable x_v = 0 means vertex v is in V1 (with s), x_v = 1 means v is in V2 (with t). Constraints: x_s = 0, x_t = 1, sum(1-x_v) <= B, sum(x_v) <= B, and total cut weight sum(w(e) * |x_u - x_v|) <= K.

Schema (data type)

Type name: MinimumCutIntoBoundedSets<G, W>
Variants: graph topology (graph type parameter G), weight type (W)

Field	Type	Description
graph	G	The undirected graph G = (V, E)
edge_weights	Vec<W>	Edge weights w: E -> Z+ (one per edge, indexed by edge index)
source	usize	Source vertex s that must be in V1
sink	usize	Sink vertex t that must be in V2
size_bound	usize	Maximum size B for each partition set
cut_bound	W	Maximum total cut weight K

Size fields (getter methods):

• num_vertices() -> usize (= |V|)
• num_edges() -> usize (= |E|)

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• The "Minimum" in the name is part of the Garey & Johnson canonical name (ND17), not an optimization prefix per the codebase conventions.
• The optimization version minimizes the cut weight subject to |V1| <= B and |V2| <= B.
• Edge weights follow the same pattern as MaxCut: stored in a separate Vec<W> field parallel to the graph's edge list.

Complexity

• Decision complexity: NP-complete (Garey & Johnson, 1979, A2 ND17; transformation from SIMPLE MAX CUT). Remains NP-complete for B = |V|/2 and unit edge weights (the minimum bisection problem).
• Best known exact algorithm: Brute-force enumeration of all 2^n vertex partitions in O(2^n) time. For minimum bisection, Cygan et al. (2014) showed it is fixed-parameter tractable (FPT) with respect to the cut size. Without the balance constraint, minimum s-t cut is solvable in polynomial time via max-flow (e.g., O(n^3) with push-relabel).
• declare_variants! guidance:

  crate::declare_variants! {
      MinimumCutIntoBoundedSets<SimpleGraph, i32> => "2^num_vertices",
  }

• Approximation: For k-way balanced graph partitioning with exact balance, no polynomial-time finite approximation factor exists unless P = NP (Andreev and Räcke, 2006). For balanced separator (relaxed balance), an O(sqrt(log n))-approximation is known (Arora, Rao, Vazirani, 2009).
• References:
  • M.R. Garey, D.S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. Problem ND17.
  • M.R. Garey, D.S. Johnson, L. Stockmeyer (1976). "Some Simplified NP-Complete Graph Problems." Theoretical Computer Science, 1(3):237-267. (Proves SIMPLE MAX CUT is NP-complete; the reduction to ND17 is in G&J 1979.)
  • M. Cygan, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, S. Saurabh (2014). "Minimum Bisection is Fixed Parameter Tractable." STOC 2014.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), weight w(e) in Z+ for each e in E, specified vertices s,t in V, positive integer B <= |V|, positive integer K.
QUESTION: Is there a partition of V into disjoint sets V1 and V2 such that s in V1, t in V2, |V1| <= B, |V2| <= B, and such that the sum of the weights of the edges from E that have one endpoint in V1 and one endpoint in V2 is no more than K?

Reference: [Garey, Johnson, and Stockmeyer, 1976]. Transformation from SIMPLE MAX CUT.
Comment: Remains NP-complete for B = |V|/2 and w(e) = 1 for all e in E. Can be solved in polynomial time for B = |V| by standard network flow techniques.

How to solve

• It can be solved by (existing) bruteforce. Enumerate all 2^n partitions of V with s in V1 and t in V2, check size bounds and compute cut weight.
• It can be solved by reducing to integer programming. Binary variable per vertex, minimize cut weight subject to s/t placement and balance constraints.
• Other: Semidefinite programming relaxation for the minimum bisection variant

Example Instance

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

• Edges with weights:
  • {0,1}: w=2, {0,2}: w=3, {1,2}: w=1, {1,3}: w=4
  • {2,4}: w=2, {3,5}: w=1, {3,6}: w=3, {4,5}: w=2
  • {4,6}: w=1, {5,7}: w=2, {6,7}: w=3, {5,6}: w=1
• Size bound B = 5

YES instance (K=6): Partition V1 = {0, 1, 2, 3}, V2 = {4, 5, 6, 7}.

• |V1| = 4 <= 5, |V2| = 4 <= 5. s=0 in V1, t=7 in V2.
• Cut edges: {2,4}(w=2), {3,5}(w=1), {3,6}(w=3). Cut weight = 2 + 1 + 3 = 6 <= K=6. Answer: YES.

NO instance (K=5): No partition of V with s=0 in V1, t=7 in V2, |V1| <= 5, |V2| <= 5 achieves cut weight <= 5.

• V1={0,1,2,4}, V2={3,5,6,7}: cut edges {1,3}(4)+{4,5}(2)+{4,6}(1) = 7 > 5.
• V1={0,1,2,3,4}, V2={5,6,7}: cut edges {3,5}(1)+{3,6}(3)+{4,5}(2)+{4,6}(1) = 7 > 5.
• All valid partitions have cut weight >= 6. Answer: NO.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph
Non-trivial	✅ Pass	Distinct from existing MaxCut — adds balance constraint and decision formulation
Correctness	⚠️ Warn	Minor reference issues; associated rule citation inconsistent with G&J
Well-written	⚠️ Warn	Example is messy with inline corrections; missing complexity string for declare_variants!

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

Pass. The problem MinimumCutIntoBoundedSets does not exist in the codebase. It is a well-known NP-complete graph partitioning problem (Garey & Johnson ND17) that combines minimum s-t cut with a balance constraint. The motivation is clear: VLSI layout, load balancing, and graph bisection. The issue mentions one associated rule (Vertex Cover -> MinimumCutIntoBoundedSets), which would connect it to the existing reduction graph.

Non-trivial

Pass. This problem is genuinely distinct from all existing problems in the codebase:

• MaxCut is an optimization problem that maximizes cut weight with no balance constraint and no designated s/t vertices. MinimumCutIntoBoundedSets is a decision problem with both a cut weight upper bound K AND a partition size upper bound B, plus designated source/sink vertices.
• No other existing problem captures this combination of constraints.
• The key insight from G&J is that removing the balance constraint makes the problem polynomial (standard max-flow), so the balance constraint is what makes it NP-complete — this is a non-trivial structural difference.

Correctness

Warn. Most claims check out, but there are issues:

1. Garey, Johnson, Stockmeyer (1976) — Verified. "Some Simplified NP-Complete Graph Problems," Theoretical Computer Science, 1(3):237-267. This paper does exist and addresses NP-completeness of simplified graph problems including max cut variants. However, the issue cites this paper for the NP-completeness of MinimumCutIntoBoundedSets, while G&J's book says the transformation is "from SIMPLE MAX CUT." The 1976 paper proves SIMPLE MAX CUT is NP-complete; the reduction to MinimumCutIntoBoundedSets would be in the book itself (1979), not the 1976 paper.

2. Cygan et al. (2014) — Verified. "Minimum Bisection is Fixed Parameter Tractable," STOC 2014, pages 323-332. Confirmed via arXiv (1311.2563) and ACM DL. The FPT result with respect to cut size is correctly stated.

3. Andreev and Racke (2006) — Verified with nuance. "Balanced Graph Partitioning," Theory of Computing Systems, 39:929-939. The paper shows no finite approximation ratio for k >= 3 partitions with nu = 1 (exact balance). The issue's claim about "no polynomial-time finite approximation factor for balanced graph partition unless P = NP" is broadly correct but slightly imprecise — the hardness depends on the exact balance parameter.

4. Arora, Rao, Vazirani (2009) — Verified. "Expander flows, geometric embeddings and graph partitioning," J. ACM, 56(2):1-37. The O(sqrt(log n)) approximation for balanced separator is correctly cited.

5. Associated rule inconsistency: The issue's "Associated rules" section claims "R38b: VERTEX COVER -> MINIMUM CUT INTO BOUNDED SETS" but the G&J book entry says the NP-completeness proof is via "Transformation from SIMPLE MAX CUT." These are different reductions. The associated rule may still be valid but needs a separate reference.

Well-written

Warn. The issue is mostly complete and well-structured, but has several issues to address:

Completeness: All required sections are present (Motivation, Name, Reference, Definition, Variables, Schema, Complexity, How to solve, Example). Good.

Definition quality: The mathematical definition is clear and well-formed, directly from G&J. The variable encoding (binary per vertex, 0=V1, 1=V2) is clean and implementable. Good.

Issues found:

1. Example quality — messy with inline corrections: The example section contains stream-of-consciousness calculations with self-corrections ("Wait: vertex 4 is in V1..."), abandoned partitions, and eventual parameter changes (K=5 to K=6). While the final answer is correct (V1={0,1,2,3}, V2={4,5,6,7} gives cut weight 6 = K for K=6), the example should be cleaned up to show:

   • One clear satisfying partition for K=6
   • One clear demonstration that no partition satisfies K=5
   • Without the inline "Wait" corrections

2. Missing complexity string for declare_variants!: The Complexity section discusses general approaches but does not provide a concrete worst-case exact algorithm time bound in the format needed for declare_variants! (e.g., "2^num_vertices"). For a general satisfaction problem solvable by brute force, this would be "2^num_vertices". The issue should specify this explicitly.

3. Schema concern — satisfaction vs optimization naming: The issue correctly identifies this as a SatisfactionProblem with Metric = bool. The "Minimum" in the name is part of the G&J canonical name, not an optimization prefix per the codebase conventions. This is acceptable but should be noted in implementation.

4. Symbol consistency: Generally good. G = (V, E), s, t, B, K are all defined and used consistently across sections. The getter methods num_vertices() and num_edges() are mentioned. Minor: the Schema table does not list edge_weights as a field — edge weights are implied by the graph field but the issue mentions w(e) in Z+, so weight handling should be clarified (is it stored in the graph or as a separate field?).

Recommendations

• Clean up the example to present one clear YES instance and one clear NO instance without inline corrections.
• Add a concrete complexity string for declare_variants! (e.g., "2^num_vertices" for brute-force).
• Clarify whether edge weights are stored in the graph type or as a separate Vec<W> field (following the pattern of MaxCut).
• Fix the associated rule reference — if the intended reduction is from Simple Max Cut (as per G&J), update accordingly; if from Vertex Cover, provide a separate citation.

🤖 Generated with Claude Code