[Rule] 3-PARTITION to MinimumGraphBandwidth

[isPANN]

Source: 3-PARTITION
Target: BANDWIDTH

Motivation: Establishes NP-completeness of BANDWIDTH via polynomial-time reduction from 3-PARTITION. This is the original proof by Papadimitriou (1976a) referenced in Garey & Johnson. The reduction is notable because it shows BANDWIDTH is NP-hard in the strong sense (since 3-PARTITION is strongly NP-complete), which means pseudo-polynomial algorithms cannot exist unless P=NP.
Reference: Garey & Johnson, Computers and Intractability, A1.1 GT40; Papadimitriou 1976a

GJ Source Entry

BANDWIDTH
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].

Reduction Algorithm

Summary:
Given a ThreePartition instance with 3m integers a_1, ..., a_{3m} summing to mB (where B/4 < a_i < B/2 for each i), construct a MinimumGraphBandwidth instance (G, K) as follows:

1. Caterpillar construction: Build a caterpillar tree (a path with pendant vertices). The backbone path has length proportional to mB + m - 1. Along this path, create m "slots" of size B separated by "separators."

2. Element gadgets: For each integer a_i, create a small tree (star or path) with a_i leaves that must be embedded contiguously in the linear arrangement.

3. Separator gadgets: Between consecutive slots, insert separator vertices that force the linear arrangement to place element gadgets into exactly m groups of total size B each.

4. Bandwidth parameter: Set K to a value that constrains the arrangement so that each slot can accommodate exactly total weight B, forcing a valid 3-partition.

5. Solution extraction: From a bandwidth-K arrangement, read off which element gadgets fall into which slot to recover the 3-partition.

The key insight is that the bandwidth constraint on a carefully designed tree forces the linear arrangement to pack element gadgets into fixed-size bins, exactly encoding the 3-PARTITION problem.

Size Overhead

Symbols:

• n = num_elements of source ThreePartition instance (= 3m)
• B = bound of source ThreePartition instance
• S = sum of all elements (= mB)

Target metric (code name)	Polynomial (using symbols above)
num_vertices	O(num_elements * bound)
num_edges	O(num_elements * bound)

Derivation:
The exact overhead depends on the specific caterpillar construction. Papadimitriou's original construction uses O(mB) vertices (backbone of length ~mB plus pendant vertices for element encoding). Since the graph is a tree, num_edges = num_vertices - 1. Note: this is a pseudo-polynomial construction, but 3-PARTITION is strongly NP-complete, so the reduction is still polynomial when input numbers are encoded in unary (as they are in the strong sense).

Validation Method

• Closed-loop test: reduce ThreePartition instance to MinimumGraphBandwidth, solve target with BruteForce, extract 3-partition from the linear arrangement, verify each group sums to B
• Test with both solvable and unsolvable 3-PARTITION instances
• Verify the constructed graph is a tree (or caterpillar) as expected
• Check that the bandwidth parameter matches the construction

Example

Source instance (ThreePartition):
m = 2, B = 10, elements = [3, 3, 4, 4, 3, 3] (6 elements, sum = 20 = 2 * 10)

Valid partition: {3, 3, 4} and {4, 3, 3}, each summing to 10.

Target instance sketch (MinimumGraphBandwidth):
A caterpillar tree with ~20+ vertices encoding the element sizes, with bandwidth K chosen so that a valid arrangement exists iff the 3-partition exists. The exact construction follows Papadimitriou's caterpillar gadgets.

(Full vertex/edge enumeration omitted due to the construction's complexity — the reduction produces O(mB) = O(20) vertices for this small instance.)

References

• Papadimitriou, C. H. (1976a). "The NP-completeness of the bandwidth minimization problem." Computing, 16(3), 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, A1.1 GT40.