[Model] GraphPartitioning

[isPANN]

---

name: Problem
about: Propose a new problem type
title: "[Model] GraphPartitioning"
labels: model
assignees: ''

Motivation

GRAPH PARTITIONING (P90) from Garey & Johnson, A2 ND14. A fundamental NP-complete graph optimization problem asking whether the vertices of a weighted graph can be partitioned into groups of bounded total vertex weight such that the total weight of edges crossing between groups is bounded. This captures the classic min-cut balanced partitioning problem that arises in VLSI circuit layout, parallel computing load balancing, and sparse matrix reordering.

Associated reduction rules:

• As target: R35b (PARTITION INTO TRIANGLES -> GRAPH PARTITIONING) via Hyafil and Rivest, 1973
• As target: R35 (MAX 2SAT -> GRAPH PARTITIONING) via Garey, Johnson, and Stockmeyer, 1976

Definition

Name: GraphPartitioning
Canonical name: GRAPH PARTITIONING
Reference: Garey & Johnson, Computers and Intractability, A2 ND14

Mathematical definition:

INSTANCE: Graph G = (V, E), weights w(v) in Z^+ for each v in V and l(e) in Z^+ for each e in E, positive integers K and J.
QUESTION: Is there a partition of V into disjoint sets V_1, V_2, ..., V_m such that sum_{v in V_i} w(v) <= K for 1 <= i <= m and such that if E' is the set of edges that have their two endpoints in two different sets V_i, then sum_{e in E'} l(e) <= J?

Variables

• Count: n = |V| variables (one per vertex), encoding the partition group assignment
• Per-variable domain: {0, 1, ..., m_max - 1} where m_max is the maximum number of groups (bounded by n in the worst case)
• Meaning: Variable i = j means vertex i is assigned to partition set V_j. A valid assignment must ensure: (1) the total vertex weight in each group is at most K, and (2) the total weight of edges crossing between different groups is at most J.

Schema (data type)

Type name: GraphPartitioning
Variants: graph topology (graph type parameter G), weight type (W)

Field	Type	Description
graph	SimpleGraph	The undirected graph G = (V, E)
vertex_weights	Vec<W>	Positive integer weight w(v) for each vertex v
edge_weights	Vec<W>	Positive integer weight l(e) for each edge e
max_part_weight	W	Upper bound K on total vertex weight per partition
max_cut_weight	W	Upper bound J on total weight of cross-partition edges

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• The number of parts m is not fixed; it is determined by the partition itself (m can range from 1 to |V|).
• When all vertex and edge weights are 1, K bounds the maximum group size and J bounds the number of cut edges.

Complexity

• Best known exact algorithm: General case requires exponential time. A brute-force approach enumerates all partitions of n vertices, checking weight constraints. The Bell number B(n) bounds the number of partitions. Subset DP approaches yield O(3^n * poly(n)) time.
• NP-completeness: NP-complete (Hyafil and Rivest, 1973). Transformation from PARTITION INTO TRIANGLES. Remains NP-complete for fixed K >= 3 even if all vertex and edge weights are 1.
• Polynomial special cases:
  • K = 2 (bisection): solvable in polynomial time by matching.
  • No polynomial-time approximation within any finite factor for the (k,1)-balanced partition variant unless P = NP.
• Heuristics: Kernighan-Lin algorithm (1970), spectral methods, multilevel approaches (METIS, etc.).
• References:
  • L. Hyafil and R. L. Rivest (1973). "Graph partitioning and constructing optimal decision trees are polynomial complete problems." IRIA-Laboria Report.
  • M. R. Garey, D. S. Johnson, and L. Stockmeyer (1976). "Some simplified NP-complete graph problems." Theoretical Computer Science 1, pp. 237--267.
  • B. W. Kernighan and S. Lin (1970). "An efficient heuristic procedure for partitioning graphs." Bell System Technical Journal 49(2), pp. 291--307.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), weights w(v) in Z^+ for each v in V and l(e) in Z^+ for each e in E, positive integers K and J.
QUESTION: Is there a partition of V into disjoint sets V_1, V_2, ..., V_m such that sum_{v in V_i} w(v) <= K for 1 <= i <= m and such that if E' is the set of edges that have their two endpoints in two different sets V_i, then sum_{e in E'} l(e) <= J?

Reference: [Hyafil and Rivest, 1973]. Transformation from PARTITION INTO TRIANGLES.
Comment: Remains NP-complete for fixed K >= 3 even if all vertex and edge weights are 1. Can be solved in polynomial time for K = 2 by matching.

How to solve

• It can be solved by (existing) bruteforce — enumerate all vertex partitions and check both weight constraints.
• It can be solved by reducing to integer programming — binary variables x_{v,j} for vertex v in group j, with vertex weight sum constraints per group and edge cut weight constraint.
• Other: Kernighan-Lin heuristic; spectral partitioning; multilevel methods (METIS).

Example Instance

Instance 1 (YES — valid partition exists):
Graph G with 8 vertices {0, 1, 2, 3, 4, 5, 6, 7} and 10 edges:

• Edges: {0,1}, {1,2}, {2,3}, {3,0}, {4,5}, {5,6}, {6,7}, {7,4}, {0,4}, {2,6}
• Vertex weights: all w(v) = 1
• Edge weights: all l(e) = 1
• K = 4 (max group weight), J = 2 (max cut weight)
• Partition: V_1 = {0, 1, 2, 3}, V_2 = {4, 5, 6, 7}
  • V_1 weight = 4 <= K=4, V_2 weight = 4 <= K=4
  • Cut edges: {0,4} and {2,6}, total cut weight = 2 <= J=2
• Answer: YES

Instance 2 (NO — no valid partition):
Graph G with 6 vertices {0, 1, 2, 3, 4, 5}, complete graph K_6 (15 edges):

• Vertex weights: all w(v) = 1
• Edge weights: all l(e) = 1
• K = 3, J = 2
• Any partition into groups of size <= 3 requires at least 2 groups. With 2 groups of 3 in K_6: cut edges = 3 * 3 = 9 >> J=2. With 3 groups of 2: each pair of groups contributes 2*2=4 cut edges, total = 12 >> J=2.
• In K_6, any non-trivial partition cuts many edges; J=2 is far too small.
• Answer: NO

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in codebase; substantive motivation
Connectivity	✅ Pass	Referenced by 5 [Rule] issues (#118, #119, #120, #121, #246)
Non-trivial	✅ Pass	Satisfaction problem with dual constraints (group weight + cut weight); distinct from all 24 existing problems
Correctness	⚠️ Warn	Main NP-completeness references verified; O(3^n) complexity bound not cited to a specific paper
Well-written	✅ Pass	All sections present and substantive; examples fully worked

Overall: 4 passed, 0 failed, 1 warning

---

Usefulness

• pred show GraphPartitioning → not found. Problem is novel.
• Motivation is substantive: VLSI circuit layout, parallel computing load balancing, sparse matrix reordering.
• How to solve: brute-force, ILP reduction, and heuristics (Kernighan-Lin, METIS) all identified.

Connectivity

Multiple [Rule] issues reference this model:

• As source: [Rule] GraphPartitioning to ILP #118 (GraphPartitioning → ILP), [Rule] GraphPartitioning to QUBO #119 (GraphPartitioning → QUBO), [Rule] GraphPartitioning to MaxCut #120 (GraphPartitioning → MaxCut), [Rule] GraphPartitioning to SpinGlass #121 (GraphPartitioning → SpinGlass)
• As target: [Rule] PARTITION INTO TRIANGLES to GRAPH PARTITIONING #246 (PartitionIntoTriangles → GraphPartitioning)

This model is well-connected in the planned reduction graph.

Non-trivial

GraphPartitioning is a satisfaction problem with dual constraints: (1) bounded group vertex weight ≤ K, and (2) bounded total cut edge weight ≤ J. No existing problem in the codebase has this combination:

• MaxCut maximizes cut weight (optimization, single objective)
• KColoring constrains adjacent vertex colors (no weight bounds)
• BinPacking partitions items by capacity (no graph/cut structure)

Genuinely distinct feasibility constraints → Pass.

Correctness

References verified:

• ✅ Hyafil and Rivest (1973): IRIA-RR-033 technical report confirmed. Shows graph partitioning is NP-complete. HAL
• ✅ Garey, Johnson, and Stockmeyer (1976): "Some Simplified NP-Complete Graph Problems", Theoretical Computer Science 1, pp. 237–267. Paper confirmed on ScienceDirect. Note: this paper focuses on simplifying existing NP-complete problems by domain restriction (Max Cut, Node Cover on planar graphs); the "R35: MAX 2SAT → GRAPH PARTITIONING" association in the issue header is marked unverified and may be inaccurate — the paper does not directly present a reduction TO graph partitioning.
• ✅ Kernighan and Lin (1970): Well-known heuristic, no verification needed.
• ✅ K = 2 polynomial by matching: Confirmed by Garey & Johnson book text (quoted in the issue).

Unverified claim:

• ⚠️ "Subset DP approaches yield O(3^n · poly(n)) time" — this bound is plausible (standard for partition-into-bounded-groups via inclusion-exclusion, cf. Koivisto 2009), but the issue cites no specific paper. Should add a citation.

Well-written

Template completeness: All 9 required sections present and substantive ✅

Definition: Precise mathematical formulation matching the Garey & Johnson book entry verbatim ✅

Variables: Count (n = |V|), domain ({0, ..., m_max-1}), and semantics clearly stated ✅

Schema: Field table with types and descriptions; correctly identifies as SatisfactionProblem with Metric = bool ✅

Symbols: All symbols (G, V, E, w(v), l(e), K, J, m) defined before use and consistent across sections ✅

Examples: Two instances provided (YES and NO cases), both non-trivial (8 vertices / 6 vertices), fully worked with step-by-step reasoning ✅

Recommendations

• Add a citation for the O(3^n · poly(n)) complexity bound (e.g., Koivisto, "Partitioning into Sets of Bounded Cardinality", 2009; or Björklund et al., "Set Partitioning via Inclusion-Exclusion", 2009)
• The "associated reduction rules" header mentions "R35: MAX 2SAT → GRAPH PARTITIONING (Garey, Johnson, and Stockmeyer, 1976)" — this attribution is likely incorrect based on the actual paper content. Consider removing or re-sourcing.
• Note: issue [Model] GraphPartitioning #117 has the same title [Model] GraphPartitioning — this may be a duplicate or superseded version. Consider closing one.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; solid motivation (VLSI, parallel computing, sparse matrix reordering)
Non-trivial	✅ Pass	Distinct feasibility constraints (weight-bounded partition + cut weight bound) from all 24 existing problems
Correctness	⚠️ Warn	Core references verified; one associated rule citation is questionable; K=2 polynomial claim is correct
Well-written	⚠️ Warn	Variable domain and number of groups need clarification for implementability; missing concrete complexity string

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

Pass. GraphPartitioning does not exist in the codebase (confirmed via pred show). The problem is a classic from Garey & Johnson (A2 ND14) with well-established applications in VLSI circuit layout, parallel computing load balancing, and sparse matrix reordering. Two associated reduction rules are proposed, connecting it to the existing reduction graph. The motivation is concrete and well-articulated.

Non-trivial

Pass. GraphPartitioning has genuinely distinct feasibility constraints from all 24 existing problems:

• It combines a partition weight bound (per-group vertex weight sum <= K) with a cut weight bound (total inter-group edge weight <= J) -- no existing problem has this dual-constraint structure.
• It is not a variant of MaxCut (which optimizes cut weight without group size constraints), nor of KColoring (which prohibits adjacent same-color but has no weight bounds), nor of BinPacking (which has capacity constraints but no graph structure).

Correctness

Warn. Core references are verified, but one associated rule citation is questionable.

Verified references:

• Hyafil & Rivest (1973): Confirmed. "Graph partitioning and constructing optimal decision trees are polynomial complete problems," IRIA-Laboria Report (IRIA-RR-033). Available at INRIA HAL and MIT. Correctly cited as the NP-completeness proof.
• Garey, Johnson, Stockmeyer (1976): Confirmed. "Some simplified NP-complete graph problems," Theoretical Computer Science 1(3), pp. 237-267. Available on ScienceDirect. However, see warning below about its association with graph partitioning.
• Kernighan & Lin (1970): Confirmed. "An efficient heuristic procedure for partitioning graphs," Bell System Technical Journal 49(2), pp. 291-307. Available on Wiley. Seminal heuristic work, correctly cited.

K=2 polynomial-time claim: Correct. When K=2 with unit vertex weights, each partition group has at most 2 vertices, reducing the problem to finding a minimum-weight matching -- solvable in polynomial time.

3^n complexity claim: Reasonable. The O(3^n * poly(n)) bound from subset DP is standard for set partition problems (enumerate subsets and their complements). This aligns with known results for similar partition problems.

Questionable association -- R35 (MAX 2SAT -> GRAPH PARTITIONING): The Garey, Johnson, Stockmeyer (1976) paper is primarily about showing NP-completeness results for simplified versions of graph problems (Simple Max Cut, restricted Node Cover, etc.). It does not appear to contain a direct reduction from MAX 2SAT to GRAPH PARTITIONING. This association is marked "unverified" in the issue, and rightly so -- it should be verified or removed before implementation.

NP-completeness transformation: The issue correctly states the transformation is from PARTITION INTO TRIANGLES (per Garey & Johnson's appendix entry). This is consistent with the Hyafil & Rivest (1973) reference.

Well-written

Warn. The issue is generally well-structured and follows the template, but has several items that need clarification for implementability:

1. Variable domain is problematic. The per-variable domain is stated as {0, 1, ..., m_max - 1} where m_max is "bounded by n in the worst case." For implementation with the Problem trait, dims() must return concrete domain sizes. Since the number of groups m is not fixed and can range from 1 to n, each variable would need domain size n. This makes brute-force enumeration produce n^n configurations, which is vastly larger than necessary (Bell number B(n) bounds actual partitions). The issue should clarify how to handle this in the dims() implementation and whether symmetry-breaking is needed.

2. Missing concrete complexity string. The declare_variants! macro requires a concrete complexity expression like "3^num_vertices". The issue mentions O(3^n * poly(n)) informally but does not provide the exact string. A suggested complexity string would be "3^num_vertices".

3. YAML front matter included. The issue body starts with YAML template metadata (---\nname: Problem\nabout: ...) that should have been consumed by the GitHub issue template, not visible in the body. This is cosmetic but clutters the issue.

4. Symbol m and m_max not well-defined. The Variables section uses m_max ("maximum number of groups") without precisely defining it. Since the number of groups is determined by the partition itself and not an input parameter, the issue should clarify that n (the number of vertices) serves as the upper bound for the variable domain.

5. Example quality is adequate. Instance 1 (YES) is fully worked with 8 vertices and a clear partition. Instance 2 (NO) with K_6 provides a good negative example with a clear argument. Both are hand-verifiable.

6. Schema is reasonable. The fields (graph, vertex_weights, edge_weights, max_part_weight, max_cut_weight) capture all input parameters. The satisfaction problem classification (Metric = bool) is correct.

Recommendations

• Clarify the dims() implementation strategy: either use domain size n for each variable (accepting redundancy from permutation symmetry), or document how symmetry-breaking will be handled.
• Add a concrete complexity string for declare_variants!, e.g., "3^num_vertices".
• Remove or verify the "R35 (MAX 2SAT -> GRAPH PARTITIONING)" association, as the cited Garey-Johnson-Stockmeyer 1976 paper does not appear to contain this specific reduction.
• Strip the YAML front matter from the issue body.

[zazabap]

This is a duplicate of #117. PR #570 already implements GraphPartitioning with all CI checks passing.