PaperlayerView exact revision on arXiv

Source-linked AI summary

Forbidden Subgraphs of Graphs with Low Bandwidth

Maria Chudnovsky, Daniel Lokshtanov, Eran Nevo

arXiv:2609.01949v1cs.DS

TL;DR

Bandwidth is notoriously hard to compute and approximate, even on restricted trees. This paper develops an FPT-approximation algorithm based on structural and embedding arguments, showing that it either finds a high-bandwidth subtree or constructs a bounded-bandwidth layout. The result resolves an open question and yields forbidden-subgraph consequences, while leaving substantial room to improve the approximation bound.

  • Problem

    Bandwidth remains computationally hard and lacks a meaningful parameterized approximation guarantee despite strong hardness results.

  • Method

    The paper combines structural decomposition with low-stretch, low-congestion embeddings to relate a graph’s bandwidth to that of a subtree.

  • Results

    2^O(9^k) · n^O(1) time yields either a subtree T with bw(T) ≥ k or a layout of G with bandwidth at most (10^85 · k^28)^4^k.

  • Takeaways & Limitations

    The theorem resolves Chung and Seymour’s question and gives a forbidden-subgraph characterization for bounded-bandwidth graphs.

  • Takeaways & Limitations

    The approximation function grows quickly with k, and the slowest possible growth remains open; the paper establishes only a double-exponential upper bound.

Abstract

from arXiv · show

A layout of a graph G is an injective function $f : V(G) \rightarrow Z$, and the bandwidth of a layout f is $bw(G,f) = max_{uv \in E(G)} |f(u) - f(v)|$. The bandwidth bw(G) of G is the minimum bandwidth of a layout of G. Computing the bandwidth of a graph is a notoriously hard problem: assuming P != NP, there is no polynomial time algorithm, even on very restricted classes of trees [Monien, SIAM Journal on Algebraic Discrete Methods, 1986], and no constant factor approximation, even on trees [Dubey et al., JCSS 2011]. Assuming the Exponential Time Hypothesis, there is no algorithm with running time $f(k)n^{o(k)}$ to determine whether an input graph has bandwidth at most k, even on very restricted classes of trees [Dregi and Lokshtanov, ICALP 2014]. In this paper we show that {\sc Bandwidth} on general graphs is FPT-approximable. In particular we give an algorithm that takes as input a graph G and an integer k, runs in time $2^{O(9^k)}n^{O(1)}$, and outputs a subtree T of G such that $bw(T) \geq k$ or a layout of G of bandwidth at most $(10^{85} k^{28})^{4^k}$. This resolves in the affirmative an open problem of Chung and Seymour [Discrete Mathematics, 1989], who asked whether the bandwidth of every graph G is upper bounded in terms of the maximum bandwidth of a subtree of G. Our theorem leads to a forbidden subgraph characterization for graphs of bounded bandwidth, and can be seen as an analog for bandwidth of the classic grid minor theorem for treewidth, the forbidden subtree theorem for pathwidth, and the forbidden subpath theorem for treedepth.

1 Introduction

Bandwidth is difficult to compute and approximate, motivating parameterized approximation. The paper gives an FPT-approximation algorithm and structural forbidden-subgraph consequences for general graphs.

  • Problem setting: Bandwidth asks for an injective integer layout minimizing the maximum edge-length, and its decision version tests whether bandwidth is at most k.The optimization version computes a minimum-bandwidth layout.
  • Hardness and motivation: Bandwidth is NP-complete and remains hard to approximate within any constant factor, even on restricted caterpillars.It is NP-complete on caterpillars with hair length at most 3.
  • Hardness and motivation: Parameterized approximation seeks an algorithm that either certifies bw(G) ≥ k or outputs a layout with bandwidth bounded by a function of k in f(k)n^O(1) time.Before this work, related problems had strong hardness-of-approximation results, suggesting Bandwidth might also resist meaningful parameterized approximation.
  • Main result: 2^O(9^k) · n^O(1) time suffices to either find a subtree T with bw(T) ≥ k or produce a layout of G with bandwidth at most (10^85 · k^28)^4^k.The theorem outputs the high-bandwidth subtree when it certifies the lower bound.
  • Structural consequences: The result resolves Chung and Seymour’s question by bounding graph bandwidth as a function of the maximum bandwidth of a subtree.It also yields a forbidden-subgraph characterization based on pathwidth, local density, and skewed Cantor combs.
  • Proof outline: The proof develops low-stretch, low-congestion embeddings with prescribed vertices and uses connected decompositions supported by small separators and low local density.The embedding theorem gives stretch at most 480(|S|+1)^3(k+1)^2s and congestion at most 1300(|S|+1)^4(k+1)r.
  • Novelty: The updated proof replaces Courcelle’s Theorem with a greedy improvement scheme, yielding double-exponential rather than non-elementary dependence on k.Using local density instead of pathwidth also improves the approximation ratio over the conference version.

2 Notation, Definitions, and Preliminary Results

This section establishes graph notation, layouts, bandwidth, embeddings, local-density measures, and pathwidth, then states structural and algorithmic preliminaries used later.

  • Embeddings and Layouts: Embeddings map vertices between graphs and are measured by stretch, congestion, and contraction; layouts are embeddings into paths with congestion 1.
  • Definitions: A layout maps vertices injectively to integers; its bandwidth is the maximum edge-span, while graph bandwidth minimizes this quantity over layouts.
  • Local Density: Bandwidth dominates local density and radial local density, while both density measures are monotone under taking subgraphs.
  • Local Density: Every connected graph contains a subtree preserving its radial local density, obtained using a breadth-first-search tree.
  • Pathwidth: Pathwidth is at most bandwidth, and a tree has pathwidth at least k + 1 exactly when three components after deleting some vertex each have pathwidth at least k.
  • Preliminary Results: Every graph either contains a subtree of pathwidth at least k or has pathwidth at most 5·3^k−1−5.

3 Manipulating Embeddings

This section develops compositional tools for embeddings, constructs low-stretch path embeddings, and converts embeddings into layouts with controlled bandwidth.

  • Embedding Composition: Embedding composition multiplies the component embeddings’ stretch, congestion, and contraction bounds.
  • Path Embeddings: Embedding a path into the infinite path with endpoint constraints uses folding, preserving stretch at most k and congestion at most 2.
  • Path Embeddings: A path can be embedded into a sufficiently large connected graph with stretch at most 2, congestion at most k, and both endpoints mapped to a prescribed vertex.
  • Path Embeddings: With prescribed endpoints a and b, a path embedding achieves stretch at most max(2, s) and congestion at most k + 1 when d_G(a,b) ≤ s·(t−1).
  • Layouts: Any embedding into the integer path with stretch s_f and congestion c_f can be converted polynomially into a layout of bandwidth at most (s_f + 1)c_f − 1.

4 Low Bandwidth Embeddings with Prescribed Vertices

The section develops embeddings of low-bandwidth graphs into trees and then into a path while preserving prescribed vertices. Its construction yields explicit bounds on leaves, stretch, congestion, and S-contraction.

  • Composition: Composing the two embeddings produces an embedding that respects the prescribed mapping on S, with stretch at most 480(|S| + 1)^3(k + 1)^2s and congestion at most 1300(|S| + 1)^4(k + 1)r.The composition is defined by g(v) = g2(g1(v)) and satisfies g(s_i) = h(s_i) for every prescribed vertex s_i.
  • Tree embeddings: The main technical result embeds any bandwidth-at-most-k graph with a small vertex set S into a tree with few leaves and controlled stretch, congestion, and S-contraction.The tree has at most 2|S| leaves, stretch at most k, congestion 1, and S-contraction at most max(2|S| −1, 2k).
  • Tree embeddings: The proof orders vertices by a bandwidth-k layout, builds prefixes V_i, and studies the connected components C_i containing each newly added vertex.The components satisfy a laminarity property: if i ≤ j and C_i intersects C_j, then C_i is contained in C_j.
  • Tree embeddings: Anchor and leaf-set relationships organize the components into a parent structure whose graph T is connected and has exactly n −1 edges.Therefore T is a tree; the laminar family of nonempty leaf sets has at most 2|S| −1 distinct members, yielding at most 2|S| leaves.
  • Tree embeddings: Every edge of G maps to vertices at tree distance at most k, because an edge between positions i and j implies C_i is contained in C_j and j −i ≤ k.The identity embedding has congestion 1, while the parent construction supplies the stretch bound.
  • Path embeddings: A tree with ℓ leaves and prescribed set S can be embedded into a path with congestion at most 4ℓ+2|S|, stretch at most 24ℓ+12|S|, and S-contraction at most 1.Combining this with the tree embedding converts the low-bandwidth graph into a path embedding with explicit bounds.

5 Tree Packings

This section develops algorithms based on pathwidth-τ tree packings, using them to detect large-pathwidth subtrees and organize graphs into structured packing configurations.

  • A pathwidth-τ tree packing is a family of pairwise disjoint connected vertex sets, each inducing a subgraph containing a subtree of pathwidth at least τ.
  • A polynomial-time procedure transforms any nonempty pathwidth-τ tree packing into one of the same size while maintaining its packing properties.
  • 2^O(9^τ)n^O(1) time suffices to decide whether a graph contains a subtree of pathwidth at least τ and, when one exists, output such a subtree.The decision and extraction procedures are given separately by Lemmas 5.2 and 5.3.
  • A polynomial-time separator routine outputs a set of at most 8n·Δ̂_r(G)/q vertices such that every component after deletion has radius less than q.
  • 36k^2|X| vertices suffice for a set S whose deletion removes every subtree of pathwidth at least τ when the graph has radial local density at most k.The algorithm outputs both the packing X and the deletion set S within 2^O(9^τ)n^O(1) time.
  • The packing graph is a path or cycle in the structured outcome, while every subpath Q has a deletion set S_Q of size at most 36d^2|V(Q)| eliminating pathwidth-τ subtrees.This outcome applies when the graph has radial local density at most d and no subtree of pathwidth at least τ+1.

6 Weak Pre-Layouts

This section defines weak pre-layouts and constructs them from pathwidth-τ tree packings using bounded separators, path embeddings, and controlled pathwidth-hitting sets.

  • Weak pre-layout definition: A weak pre-layout is a seven-tuple encoding a graph embedding into an alternating path of positions p_i and separators s_i, together with sets controlling removed vertices and pathwidth obstructions.Its parameters include separator size s and pathwidth-τ tree hitting bound ρ.
  • Weak pre-layout definition: A weak pre-layout requires separator size at most s, neighborhood containment N(R)⊆S, stretch at most 1, connected parts, bounded separator fibers, and pathwidth-hitting conditions.The conditions also bound |W∩R| and exclude pathwidth-τ subtrees from specified residual subgraphs.
  • Illustration: Figure 2 illustrates a weak pre-layout with ℓ=5, whose path P has alternating p_i and s_i positions.
  • Construction guarantee: 1566d^3 vertices suffice for a deletion set eliminating all pathwidth-τ subtrees; otherwise the algorithm outputs a weak pre-layout with separator size at most 4d and hitting bound 792d^3.The construction runs in 2^O(9^τ)·n^O(1) time under radial local density at most d and no subtree of pathwidth at least τ+1.
  • Construction: The construction partitions the packing path or cycle into blocks P_i of 6d+1 vertices and intervening blocks J_i of between 4d+1 and 7d+1 vertices.The resulting number of path segments is ℓ=⌊r/(10d+2)⌋−1.
  • Construction: Each intervening block receives a separator Z_i of size at most 4d that separates its endpoint regions, enabling the embedding into the weak pre-layout path.The regions A_i, B_i, R_i, and Z_i partition each block and satisfy N(R_i)⊆Z_i.
  • Embedding: The embedding maps separators to s_i and assigns the remaining regions to neighboring p_i positions so that adjacent graph structure has stretch at most 1.The construction also ensures the designated end and inner parts are connected.

7 Embedding Into a Subtree

The section constructs a scaffolding tree H between a graph’s pre-layout and witness tree, then composes embeddings while controlling stretch and congestion. This yields either a large-bandwidth subtree or a bounded-bandwidth layout.

  • Pre-layouts and witness trees: Pre-layouts assign bandwidth-bounded layouts to graph parts arranged along a path, while the witness tree contains each part in a nearby subtree.Each subtree T_i contains the relevant part and lies within the neighboring parts’ vertex sets.
  • Path structure: Shortest paths between consecutive separator regions are confined to three consecutive path locations and are pairwise internally vertex-disjoint.These properties support the tree-like organization of the scaffolding graph.
  • Scaffolding embeddings: The scaffolding construction embeds each graph part into H, makes consecutive embeddings agree on separator vertices, and limits how many parts use any vertex of H.H is then embedded back into the witness tree T.
  • Anchor vertices: Anchor vertices lie in separator regions and route paths between consecutive regions with at most twice the original distance.Lemma 7.3 also bounds consecutive anchor distances in T by three times their graph distance.
  • Embedding bounds: The composed embedding has stretch at most 96000(s + 2)^4(β + 1)^2 and congestion at most 84000(s + 1)^4(β + 1).The stretch is controlled by the worst part embedding, while congestion increases by at most a factor of two.
  • Embedding bounds: Given separator size s, part bandwidth β, and integer k, Lemma 7.10 outputs either a subtree of bandwidth at least k or a layout of bandwidth at most 10^54(s + 2)^11(β + 1)^3k^3.

8 Proof of the Main Result

The main proof recursively decomposes graphs using radial density and weak pre-layouts, applies the embedding lemma to recursively obtained part layouts, and propagates either a bandwidth witness subtree or a global layout bound.

  • Recursive framework: Lemma 8.1 runs in time 2^O(9^k) n^O(1) and returns either a subtree of bandwidth at least k or a layout of bandwidth at most β(k,τ) = (10^85 · k^28)^4^τ.
  • Recursive framework: If radial local density is at least k + 1, the algorithm directly outputs a subtree with bandwidth at least k; otherwise the graph has maximum degree at most 2k.
  • Recursive framework: When a small separator S is found, recursion on G − S either finds a large-bandwidth subtree or extends its layout across S using a bounded-degree extension lemma.The resulting bound is 37584 · d^3k · β(k,τ − 1), then bounded by 10^85 · k^28 · β(k,τ − 1).
  • Pre-layout recursion: For a weak pre-layout, the proof recursively lays out each part and the residual region after removing separator and hitting-set vertices, producing a pre-layout with separator size at most 4d.
  • Pre-layout recursion: Lemma 7.10 converts this pre-layout into either a subtree of bandwidth at least k or a layout of G − (S ∪ R), after which the removed regions and separator are reinserted.
  • Runtime and theorem: The recursion depth is at most τ, and each recursive call uses disjoint vertex sets, yielding total running time 2^O(9^k) n^O(1).
  • Runtime and theorem: Theorem 1.1 therefore outputs a subtree T with bandwidth at least k or a layout of G with bandwidth at most (10^85 · k^28)^4^k.
  • Forbidden-subgraph consequence: Applying Theorem 1.1 after bounding every subtree’s bandwidth by (5k)^6k yields a forbidden-subgraph bandwidth bound of 4^4(5k)^7k.

9 Conclusion

The conclusion emphasizes the theorem’s FPT-approximation guarantee and identifies substantial room to improve its rapidly growing approximation function. It also notes an alternative polynomial-time implementation with trade-offs.

  • Main result: The algorithm runs in time 2^O(9^k) n^O(1) and either outputs a subtree of bandwidth at least k or a layout of bandwidth at most (10^85 · k^28)^4^k.
  • Open questions: The paper leaves open the slowest function h such that graphs with no subtree of bandwidth at least k have bandwidth at most h(k).The algorithm establishes that h(k) is at most double exponential in k, while no super-linear lower bound is known to the authors.
  • Implementation trade-off: A simple trick can make the algorithm polynomial-time even when k is part of the input, but adds a small approximation factor and removes the guarantee of outputting the witness subtree.
  • Main result: Theorem 1.1 shows that Bandwidth is FPT-approximable, despite the absence of constant-factor polynomial-time approximation unless P = NP.
Loading 2609.01949v1…