[Model] MinimumGraphBandwidth

[QingyunQian]

Motivation

Add the Graph Bandwidth problem, a classic graph layout optimization problem from combinatorial optimization. The goal is to label vertices of a graph with distinct integers so that the maximum difference between labels of adjacent vertices is minimized. This problem is notable for being NP-complete even for very restricted graph classes (trees with maximum degree 3), having strong inapproximability results (NP-hard to approximate within any constant factor), and introducing a minimax permutation paradigm — fundamentally different from existing problems in the project, which are subset selection (MaxCut, MaximumClique), additive permutation optimization (TravelingSalesman), or constraint satisfaction (KColoring, SAT).

Definition

Name: MinimumGraphBandwidth
Reference:

• Papadimitriou, C. H. (1976). "The NP-Completeness of the bandwidth minimization problem." Computing, 16, 263–270.
• Garey, M. R., Graham, R. L., Johnson, D. S., & Knuth, D. E. (1978). "Complexity results for bandwidth minimization." SIAM Journal on Applied Mathematics, 34(3), 477–495.
• Garey, M. R. & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Problem GT40.
• Graph bandwidth (Wikipedia)

Given an undirected graph G = (V, E) with |V| = n vertices, find a bijective labeling f: V → {0, 1, ..., n−1} that minimizes the bandwidth:

B(f, G) = max { |f(u) − f(v)| : (u, v) ∈ E }

The bandwidth of G is B*(G) = min_f B(f, G), taken over all bijective labelings f.

Decision version: Given G and integer k, is B*(G) ≤ k?

Note: Both the unweighted and weighted variants are special cases of the Quadratic Bottleneck Assignment Problem. This proposal covers the unweighted version; the weighted generalization (minimize max { w_{uv} · |f(u) − f(v)| }) can be added as a future extension.

Variables

• Count: n (number of vertices)
• Per-variable domain: n (each vertex is assigned a label from {0, 1, ..., n−1})
• Meaning: config[i] ∈ {0, 1, ..., n−1} represents the position assigned to vertex i on the number line
• Constraint: the assignment must be a bijection (all labels distinct, i.e., a permutation)

Schema (data type)

Type name: MinimumGraphBandwidth
Variants: graph type G (e.g., SimpleGraph)

Field	Type	Description
graph	G	The underlying undirected graph G = (V, E)

Complexity

• Best known exact algorithm: O*(4.473^n) by Cygan and Pilipczuk (2010), using an exponential-time algorithm based on subset convolution over subsets of vertices; for fixed bandwidth bound k, the decision problem "bandwidth ≤ k?" is solvable in O(n^k) time by dynamic programming (Gurari & Sudborough, 1984)
• Complexity class: NP-complete (Papadimitriou, 1976); remains NP-complete even for trees with maximum vertex degree 3 (Garey, Graham, Johnson & Knuth, 1978)
• Approximation hardness: NP-hard to approximate within any constant factor, even for caterpillar trees with maximum hair length 2 (Dubey, Feige & Unger, 2010); best known approximation ratio for general graphs is O(log³n · √(log log n)) via SDP (Feige, 2000; Dunagan & Vempala, 2001)
• Special cases: Bandwidth ≤ 2 is decidable in linear time (Garey et al., 1978); for any fixed k, bandwidth ≤ k is in P with O(n^k) complexity
• References:
  • Papadimitriou, C. H. (1976). "The NP-Completeness of the bandwidth minimization problem." Computing, 16, 263–270.
  • Garey, M. R., Graham, R. L., Johnson, D. S., & Knuth, D. E. (1978). "Complexity results for bandwidth minimization." SIAM J. Appl. Math., 34(3), 477–495.
  • Gurari, E. M. & Sudborough, I. H. (1984). "Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem." J. Algorithms, 5, 531–546.
  • Cygan, M. & Pilipczuk, M. (2010). "Exact and approximate bandwidth." Theoretical Computer Science, 411(40–42), 3701–3713.
  • Dubey, C., Feige, U. & Unger, W. (2010). "Hardness results for approximating the bandwidth." J. Comput. Syst. Sci., 77, 62–90.
  • Feige, U. (2000). "Approximating the bandwidth via volume respecting embeddings." J. Comput. Syst. Sci., 60(3), 510–539.

Extra Remark

Relationship to existing problems:

Problem	MinimumGraphBandwidth	Key Difference
TravelingSalesman	Both are graph optimization on permutations	TSP: minimize sum of edge costs over a Hamiltonian cycle; Bandwidth: minimize max of edge spans over a vertex labeling
KColoring	Both assign labels to vertices of a graph	KColoring: k colors, no ordering semantics, satisfaction problem; Bandwidth: n positions on a line, ordering matters, optimization problem
MaxCut	Both are graph optimization problems	MaxCut: binary partition (2 groups), maximize total cut weight; Bandwidth: full permutation (n positions), minimize maximum span
ILP	Target for reduction	Bandwidth can be encoded as an integer assignment problem with bottleneck constraints

Why MinimumGraphBandwidth is distinct:

• Objective type: Minimax (minimize the maximum edge span) — the only such problem in the project; existing optimization problems use additive objectives (minimize/maximize a sum)
• Configuration space: Permutation (bijective labeling of n vertices to n positions) — shared only with TSP, but TSP selects edges while Bandwidth assigns positions
• Problem type: OptimizationProblem (Minimize)

Applications:

• Sparse matrix reordering: Minimizing matrix bandwidth reduces fill-in during Gaussian elimination and improves cache locality for banded solvers; the Cuthill–McKee algorithm is a widely-used heuristic for this
• VLSI circuit layout: Standard cell placement in a single row to minimize maximum wire length (proportional to propagation delay)
• Finite element methods: Mesh vertex numbering to reduce bandwidth of stiffness matrices, enabling efficient banded matrix solvers

How to solve

• It can be solved by bruteforce (enumerate all n! vertex permutations)
• Specialized heuristics: Cuthill–McKee / Reverse Cuthill–McKee algorithms

Example Instance

2×3 Grid P₂ × P₃ — bandwidth = 2

Graph:
  0 — 1 — 2
  |   |   |
  3 — 4 — 5

Vertices: {0, 1, 2, 3, 4, 5}
Edges: {(0,1), (1,2), (0,3), (1,4), (2,5), (3,4), (4,5)}

Column-major labeling: f(0)=0, f(3)=1, f(1)=2, f(4)=3, f(2)=4, f(5)=5
Verification (bijection): labels = {0, 1, 2, 3, 4, 5} ✓

Edge spans:
  (0,1): |0−2| = 2
  (1,2): |2−4| = 2
  (0,3): |0−1| = 1
  (1,4): |2−3| = 1
  (2,5): |4−5| = 1
  (3,4): |1−3| = 2
  (4,5): |3−5| = 2

Bandwidth = max(2, 2, 1, 1, 1, 2, 2) = 2

Optimality: φ(P_m × P_n) = min(m, n) = min(2, 3) = 2
(Chvátalová, 1975).

Suboptimal labelings (for round-trip testing):

• Row-major f(0)=0, f(1)=1, f(2)=2, f(3)=3, f(4)=4, f(5)=5 → bandwidth = max(|0−3|, |1−4|, |2−5|, ...) = 3
• Identity labeling on the 0-indexed graph gives bandwidth 3, not 2 — the column-major ordering is strictly better

Validation Method

• Verify against known closed-form bandwidth formulas:
  • Path P_n: φ = 1
  • Complete graph K_n: φ = n − 1
  • Cycle C_n (n ≥ 3): φ = 2
  • Star K_{1,k}: φ = ⌊(k−1)/2⌋ + 1
  • Grid P_m × P_n: φ = min(m, n) (Chvátalová, 1975)
  • Complete bipartite K_{m,n} (m ≥ n ≥ 1): φ = ⌊(m−1)/2⌋ + n
• Cross-check with brute-force solver on small instances

[isPANN]

Closing as duplicate — this problem is covered by the Garey & Johnson extraction (P63 Bandwidth, G&J Appendix A1.5, GT40). 'GraphBandwidth' and 'Bandwidth' refer to the same problem. The extracted reference issue in references/Garey&Johnson/issues/models/P63_bandwidth.md provides a comprehensive definition from the original source.

[GiggleLiu]

Reopening: this is the only dedicated [Model] issue for GraphBandwidth. The G&J extraction catalog (#183) is a bulk tracking issue, not a replacement for this specific model proposal. Rule issues #134, #136, #137 depend on this model.

[GiggleLiu]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem; 3 planned rule issues (#134, #136, #137) connect it to the graph
Non-trivial	✅ Pass	Unique minimax-on-permutation paradigm; distinct from OLA (sum) and TSP (cycle)
Correctness	⚠️ Warn	References verified; complexity claim "O(n!) best known" is incorrect — O*(4.473^n) exists
Well-written	⚠️ Warn	Decision vs optimization framing mismatch with existing rules and codebase patterns

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

Pass. GraphBandwidth is not in the codebase (pred show GraphBandwidth fails). Three rule issues already exist that connect it to the reduction graph:

• [Rule] BinPacking (3-Partition) to MinimumGraphBandwidth #134: 3-Partition → GraphBandwidth (incoming)
• [Rule] MinimumGraphBandwidth to ILP #136: GraphBandwidth → ILP (outgoing)
• [Rule] GraphBandwidth to KSatisfiability #137: GraphBandwidth → KSatisfiability (outgoing)

The motivation is strong: sparse matrix reordering, VLSI layout, finite element methods. This would be the only minimax permutation problem in the graph.

Non-trivial

Pass. GraphBandwidth has a fundamentally different objective from all existing problems:

• vs OptimalLinearArrangement: OLA minimizes the sum of edge spans; GraphBandwidth minimizes the maximum edge span. Different objective function, different optimal labelings.
• vs TravelingSalesman: TSP selects edges forming a Hamiltonian cycle; Bandwidth assigns vertex positions.
• vs QuadraticAssignment: QAP minimizes a sum over all pairs; Bandwidth minimizes a max over edges only.

This is genuinely a new objective type.

Correctness

Warn. All references are verified but the complexity claim is incorrect.

References verified:

• Papadimitriou (1976) — Confirmed. Computing, 16, 263–270. Proves NP-completeness of graph bandwidth for general graphs. [Springer link valid]
• Garey, Graham, Johnson & Knuth (1978) — Confirmed. SIAM J. Appl. Math., 34(3), 477–495. Proves NP-completeness for trees with max degree 3 and gives linear-time algorithm for bandwidth ≤ 2.
• Gurari & Sudborough (1984) — Confirmed. J. Algorithms, 5, 531–546. Proves O(n^k) DP for fixed bandwidth bound k.

Complexity error: The issue states "Best known exact algorithm: O(n!) by exhaustive search." This is incorrect. The best known exact algorithm is O*(4.473^n) by Cygan and Pilipczuk (2010):

Year	Authors	Time	Reference
—	(brute force)	O*(n!)	Exhaustive search
2000	Feige & Kilian	O*(10^n)	SWAT 2000
2008	Cygan & Pilipczuk	O*(5^n)	WG 2008
2010	Cygan & Pilipczuk	O*(4.473^n)	TCS 411(40-42), 3701–3713

The declare_variants! complexity string should be 4.473^num_vertices, not factorial(num_vertices).

Well-written

Warn. The issue is otherwise excellent — all sections present, 3 well-worked examples, formal definition, validation method. But there is a framing mismatch:

Decision vs Optimization:

The issue proposes OptimizationProblem (Minimize), but:

1. Rule [Rule] GraphBandwidth to KSatisfiability #137 (GraphBandwidth → KSatisfiability) explicitly targets the decision version: "is B*(G) ≤ k?" with a bandwidth bound parameter
2. The codebase analog OptimalLinearArrangement is implemented as a SatisfactionProblem with a bound field — not as an optimization problem
3. The G&J entry (GT40) defines bandwidth as a decision problem: "Given G and integer K, is B(G) ≤ K?"

If modeled as a satisfaction problem (like OLA), the schema would include a bound field and the name "GraphBandwidth" (without "Minimum" prefix) is appropriate. If modeled as optimization, it should be named "MinimumGraphBandwidth" per codebase conventions.

Other minor notes:

• The Chvátalová (1975) citation for grid bandwidth is mentioned but not in the References section
• The DOI links for Papadimitriou (1976) and Garey et al. (1978) are valid

Recommendations

• Update the complexity to O*(4.473^n) and cite Cygan & Pilipczuk (2010), "Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time" — or more specifically their bandwidth paper in TCS 2010
• Decide on decision (SatisfactionProblem with bound, name "GraphBandwidth") vs optimization (OptimizationProblem Minimize, name "MinimumGraphBandwidth"). Recommendation: use the decision version to match OLA, G&J, and rule [Rule] GraphBandwidth to KSatisfiability #137
• If decision version: add a bound field to the Schema and update the Variables section accordingly
• Add Chvátalová (1975) to the References section

[GiggleLiu]

Fix-issue changelog

• Renamed problem from GraphBandwidth to MinimumGraphBandwidth — follows codebase convention for minimization problems (like MinimumVertexCover, MinimumFeedbackArcSet)
• Changed problem type from decision to OptimizationProblem (Minimize) — matches project preference for optimization over decision versions (like MIS, SpinGlass, TSP)
• Updated best known complexity from O(n!) brute force to O(4.473^n)* — citing Cygan & Pilipczuk (2010), "Exact and approximate bandwidth", TCS 411(40–42), 3701–3713
• Added Cygan & Pilipczuk (2010) to References section
• Consolidated from 3 example instances down to 1 (P₂×P₃ grid) — richest structure for round-trip testing
• Added suboptimal labeling comparison (row-major → bandwidth 3 vs column-major → bandwidth 2)

Applied by /fix-issue.