[Model] MinimumGraphBandwidth

[isPANN]

Motivation

BANDWIDTH (GT40) from Garey & Johnson, A1.1. Given a graph, find a linear arrangement of vertices minimizing the maximum stretch of any edge. NP-complete even for trees with maximum degree 3 (Garey, Graham, Johnson, Knuth 1978). Applications in sparse matrix ordering, circuit layout, and finite-element mesh numbering.

Associated rules:

• [Rule] 3-PARTITION to MinimumGraphBandwidth #879: ThreePartition → MinimumGraphBandwidth (NP-completeness proof, Papadimitriou 1976)

Definition

Name: MinimumGraphBandwidth
Reference: Garey & Johnson, Computers and Intractability, A1.1 GT40; Papadimitriou 1976

Mathematical definition:

INSTANCE: Graph G = (V,E).
OBJECTIVE: Find a one-to-one mapping f: V → {1, 2, ..., |V|} that minimizes max_{(u,v) ∈ E} |f(u) - f(v)|.

Variables

• Count: |V| (one per vertex)
• Per-variable domain: {1, 2, ..., |V|} (a permutation)
• Meaning: The position f(v) assigned to each vertex v. The assignment must be a bijection. The objective minimizes the maximum absolute position difference along any edge.

Schema (data type)

Type name: MinimumGraphBandwidth
Variants: graph: SimpleGraph

Field	Type	Description
graph	SimpleGraph	The input graph G = (V,E)

Notes:

• This is an optimization problem: Value = Min<usize>.
• Key getter methods: num_vertices() (= |V|), num_edges() (= |E|).

Complexity

• Decision complexity: NP-complete (Papadimitriou, 1976; transformation from 3-PARTITION). NP-complete even for trees with maximum degree 3 (Garey, Graham, Johnson, Knuth, 1978).
• Best known exact algorithm: O*(n!) by brute-force over all permutations. For trees, O*(c^n) exact algorithms exist (Bodlaender et al., 2000).
• Concrete complexity expression: "factorial(num_vertices)" (for declare_variants!)
• Special cases: Polynomial for proper interval graphs, caterpillars with hair length ≤ 1, and paths.
• Approximation: NP-hard to approximate within any constant factor for general graphs.
• References:
  • C.H. Papadimitriou (1976). "The NP-Completeness of the Bandwidth Minimization Problem." Computing 16, pp. 263-270.
  • M.R. Garey, R.L. Graham, D.S. Johnson, D.E. Knuth (1978). "Complexity Results for Bandwidth Minimization." SIAM J. Appl. Math. 34, pp. 477-495.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), positive integer K ≤ |V|.
QUESTION: Is there a one-to-one mapping f: V → {1,2,...,|V|} such that |f(u) - f(v)| ≤ K for all {u,v} ∈ E?

Reference: [Papadimitriou, 1976a]. Transformation from 3-PARTITION.
Comment: NP-complete even if G is a tree with maximum vertex degree 3 [Garey, Graham, Johnson, and Knuth, 1978].

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all |V|! permutations; compute bandwidth for each.)
• It can be solved by reducing to integer programming. (Binary assignment variables x_{v,p}; bijection + minimize max edge stretch. Companion rule issue to be filed separately.)
• Other:

Example Instance

Input: Star graph S_4 (center c=0, leaves 1,2,3):
V = {0, 1, 2, 3}, E = {(0,1), (0,2), (0,3)}

Optimal ordering: f(0)=2, f(1)=1, f(2)=3, f(3)=4. Max stretch = |2-4| = 2.
Optimal value: Min(2) — center must be adjacent to 3 leaves; placing it at position 2 (or 3) minimizes the maximum distance.

Non-trivial instance: 6 vertices, 7 edges:
V = {0,1,2,3,4,5}, E = {(0,1), (0,3), (1,2), (1,4), (2,5), (3,4), (4,5)}

The identity ordering gives bandwidth 3 (edge (0,3): |1-4|=3). The optimal ordering f = (0→1, 1→3, 2→5, 3→2, 4→4, 5→6) achieves bandwidth 2:

• (0,1): |1-3|=2, (0,3): |1-2|=1, (1,2): |3-5|=2, (1,4): |3-4|=1, (2,5): |5-6|=1, (3,4): |2-4|=2, (4,5): |4-6|=2

Optimal value: Min(2) — 4 optimal permutations out of 720 total.

Python validation script

from itertools import permutations

# S4
edges_s4 = [(0,1),(0,2),(0,3)]
min_bw = min(max(abs(p[u]-p[v]) for u,v in edges_s4) for p in permutations(range(4)))
assert min_bw == 2
print(f"S4 bandwidth: {min_bw}")

# 6-vertex example
edges = [(0,1),(0,3),(1,2),(1,4),(2,5),(3,4),(4,5)]
min_bw6 = min(max(abs(p[u]-p[v]) for u,v in edges) for p in permutations(range(6)))
opt_count = sum(1 for p in permutations(range(6)) if max(abs(p[u]-p[v]) for u,v in edges) == min_bw6)
assert min_bw6 == 2
assert opt_count == 4
print(f"6v bandwidth: {min_bw6} ({opt_count} optimal)")

# Verify specific ordering
f = {0:0, 1:2, 2:4, 3:1, 4:3, 5:5}
bw = max(abs(f[u]-f[v]) for u,v in edges)
assert bw == 2
print(f"Specific ordering verified: bandwidth={bw}")

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	❌ Fail	No planned reductions to/from existing problems mentioned
Non-trivial	✅ Pass	Distinct vertex-ordering feasibility problem, not isomorphic to any existing model
Correctness	⚠️ Warn	Complexity string uses brute-force factorial(n) despite better O*(4.83^n) known; minor attribution errors
Well-written	❌ Fail	Missing expected outcome, example too trivial, decision/optimization framing inconsistent

Overall: 1 passed, 1 warning, 2 failed

---

Usefulness

The problem MinimumGraphBandwidth does not yet exist in the codebase — pred show MinimumGraphBandwidth returns "Unknown problem". However, the issue body mentions no concrete reduction rules connecting this problem to the existing reduction graph. The "How to solve" section checks brute-force only and explicitly leaves the ILP box unchecked. There is no "Reduction Rule Crossref" section linking to a companion [Rule] issue.

Verdict: Fail — An orphan node without any planned reduction rule has no value in the reduction graph. The issue must add at least one planned reduction to/from an existing problem (e.g., a [Rule] MinimumGraphBandwidth to ILP companion, or a reduction from/to another vertex-ordering problem).

Non-trivial

The graph bandwidth problem asks for a vertex permutation minimizing the maximum edge stretch — this is a genuinely distinct feasibility/optimization problem. It is not isomorphic to any existing model in the codebase. The closest existing problems are other graph-ordering problems, but none share the same objective or constraints.

Verdict: Pass.

Correctness

3a: Definition correctness — The formal definition is mathematically well-formed and matches the standard formulation from Garey & Johnson (GT40, A1.1).

3b: Complexity verification:

• Papadimitriou 1976 — Confirmed. "The NP-Completeness of the bandwidth minimization problem," Computing 16, pp. 263–270, 1976. Correct reference.
• Garey, Graham, Johnson, Knuth 1978 — Confirmed. "Complexity results for bandwidth minimization," SIAM J. Appl. Math. 34(3), pp. 477–495, 1978. NP-complete for trees with max degree 3. Correct.
• Monien and Sudborough 1981 for caterpillars with hair length >= 2 — Partially incorrect. Monien and Sudborough (1981) published "Bandwidth Constrained NP-Complete Problems" at STOC 1981, but the specific result about caterpillars with hair length 3 being NP-complete is due to Monien (solo author, 1986), published in SIAM J. Algebraic Discrete Methods 7(4). The attribution and year in the issue are off.
• "Bodlaender et al. (2000) give an O(c^n) algorithm"* — The year is wrong. The relevant paper is Bodlaender, Fomin, Koster, Kratsch, and Thilikos, "A Note on Exact Algorithms for Vertex Ordering Problems on Graphs," Theory of Computing Systems 50(3), pp. 420–432, 2012 (not 2000). This paper achieves O*(2^n) time. Additionally, Cygan and Pilipczuk, "Even Faster Exact Bandwidth," ACM Trans. Algorithms 8(1), 2012, achieve O*(4.83^n) time with polynomial space.
• Complexity string factorial(num_vertices) — This is the naive brute-force bound (enumerate all n! permutations). The best known exact algorithm is O*(2^n) (Bodlaender et al. 2012) or O*(4.83^n) with polynomial space (Cygan & Pilipczuk 2012). The complexity string should reflect the best known algorithm, not brute force.

3c: Representation feasibility — The schema (SimpleGraph + usize bandwidth) can represent the stated problem domain. Pass.

Verdict: Warn — References are mostly verifiable but contain attribution/year errors, and the complexity string does not reflect the best known algorithm.

Recommendation: Update the complexity string to "4.83^num_vertices" (Cygan & Pilipczuk 2012, polynomial space) or "2^num_vertices" (Bodlaender et al. 2012, exponential space), and fix the Bodlaender citation year from 2000 to 2012 and the Monien caterpillar citation from "Monien and Sudborough 1981" to "Monien 1986".

Well-written

4a: Information completeness:

• Motivation: Present and substantive. Pass.
• Name: MinimumGraphBandwidth — follows naming conventions with Minimum prefix. Pass.
• Reference: Present (Garey & Johnson, Papadimitriou 1976). Pass.
• Definition: Present and formal. Pass.
• Variables: Present. Pass.
• Schema: Present with field table. Pass.
• Complexity: Present but uses brute-force bound instead of best known. See Correctness above.
• How to solve: Brute-force checked. No ILP claimed. Pass.
• Example Instance: Present but has issues (see 4d).
• Expected Outcome: Missing. The example describes YES/NO answers but does not provide a concrete optimal solution with the optimal objective value for the optimization framing, nor a concrete valid assignment with justification for the decision framing. Fail.

4b: Definition completeness — The definition presents both the decision version (with parameter K) and the optimization version (minimize bandwidth). However, the issue title says "MinimumGraphBandwidth" (optimization), while the schema includes a bandwidth field (suggesting the decision version with a threshold K). The framing is inconsistent: is this an optimization problem (find the minimum bandwidth) or a decision/feasibility problem (is bandwidth <= K)? This must be clarified, as it affects the Value type (Min vs Or). Fail.

4c: Symbol and notation consistency — Symbols are generally consistent (G, V, E, K, f). Pass.

4d: Example quality:

• The path graph P4 with K=1 is too trivial — a path is the simplest possible graph and the identity mapping trivially achieves bandwidth 1. This does not exercise the core difficulty of the bandwidth problem (finding non-obvious vertex orderings).
• The star graph example is a NO instance, which is fine for illustration, but neither example has multiple feasible configurations with different bandwidth values to test correctness.
• For a round-trip test, the example should have a graph where the optimal bandwidth is non-trivial to find (e.g., a small cycle or a tree where the identity ordering is suboptimal). The instance should have at least 2 suboptimal feasible solutions.
• Fail — example too simple for meaningful testing.

Verdict: Fail — Missing expected outcome, inconsistent decision/optimization framing, example too trivial.

Recommendations

• Clarify whether this is an optimization problem (minimize bandwidth, Value = Min<usize>) or a decision problem (bandwidth <= K, Value = Or). The name "MinimumGraphBandwidth" suggests optimization.
• If optimization: remove the bandwidth field from the schema (it becomes the objective value). If decision: keep bandwidth as threshold K and use Value = Or.
• Replace the example with a more interesting graph (e.g., a 5- or 6-vertex graph where the optimal ordering is not the identity) and provide the optimal solution explicitly.
• Add at least one planned reduction (e.g., [Rule] MinimumGraphBandwidth to ILP) to connect this problem to the reduction graph.
• Update the complexity string and fix the citation errors noted above.

[isPANN]

Converted from decision to optimization framing: removed bound K from schema, objective is now to minimize the bandwidth (max edge stretch over all vertex orderings). Cleaned up example. Companion rule issue to follow.

[isPANN]

Fix-issue changelog

• Associated rules: Linked [Rule] 3-PARTITION to MinimumGraphBandwidth #879 (ThreePartition → MinimumGraphBandwidth).
• Example: Added non-trivial 6-vertex instance (bandwidth=2, identity ordering gives 3; optimal ordering (0,2,4,1,3,5) achieves 2). Kept S4 as simpler example.
• Complexity: Added concrete expression "factorial(num_vertices)". Added Papadimitriou (1976) and Garey et al. (1978) references.
• Schema notes: Added Value = Min<usize> and getter methods.
• ILP: Added companion rule note.
• Added Python validation script (4 optimal permutations out of 720).

Applied by /fix-issue.