An Exponential Time 2-Approximation Algorithm for Bandwidth

Martin Fürer, Serge Gaspers, Shiva Prasad Kasiviswanathan

Abstract

The Graph Bandwidth problem is a classic NP-hard challenge in combinatorial optimization with significant barriers to both exact solution and approximation. This paper introduces a novel 2-approximation algorithm that breaks the $O(2^n)$ time barrier, achieving a running time of $O(1.9797^n)$ while maintaining polynomial space complexity. The approach leverages bucket-based decompositions combined with a hybrid strategy of divide-and-conquer and dynamic programming, effectively narrowing the search space for vertex arrangements.

Introduction

The bandwidth of a graph $G$ is a measure of the minimum possible maximum distance between adjacent vertices when the vertices are mapped to distinct integers from $1$ to $n$. Formally, for a graph $G=(V, E)$, the bandwidth $B(G)$ is defined as:

$$B(G) = \min_{\sigma} \max_{\{u,v\} \in E} |\sigma(u) - \sigma(v)|$$

where $\sigma: V \to \{1, \dots, n\}$ is a linear ordering (permutation) of the vertices. This problem is notoriously difficult: it is NP-hard even for simple structures like trees and is known to be hard to approximate within any constant factor in polynomial time. Given these constraints, research has shifted toward "moderately exponential" algorithms—those that improve upon exhaustive search while still operating in exponential time. This paper presents a significant breakthrough in this domain, providing the first 2-approximation algorithm to run faster than $O(2^n)$.

The Bucket Decomposition Framework

The primary innovation of this work is the use of Bucket Decompositions as a proxy for linear orderings. Instead of determining the exact position of every vertex, the algorithm partitions the vertex set $V$ into an ordered sequence of "buckets" $B_1, B_2, \dots, B_k$, each of a fixed size $\ell$.

A bucket arrangement is valid if every edge in the graph connects vertices that reside either in the same bucket or in adjacent buckets. The authors establish a critical relationship between these arrangements and the graph's bandwidth:

  1. If a graph admits a bucket arrangement with bucket size $\ell$, its bandwidth is at most $2\ell - 1$.
  2. If no such arrangement exists for a given $\ell$, the bandwidth must be at least $\ell + 1$.

By searching for the minimum $\ell$ that allows for a valid bucket decomposition, the algorithm naturally yields a 2-approximation of the optimal bandwidth.

Algorithmic Design

To determine the existence of a bucket arrangement efficiently, the authors employ two distinct techniques depending on the number of buckets $k$:

1. Divide-and-Conquer (Large $k$)

When the number of buckets is large (implying a small bucket size $\ell$), the algorithm uses a recursive strategy. It identifies a "middle" bucket, iterates through all possible vertex assignments for that bucket, and then recursively solves the independent subproblems generated for the buckets to the left and right. This approach is particularly effective when the constraints imposed by the middle bucket significantly prune the remaining search space.

2. Dynamic Programming (Small $k$)

For instances with a small, constant number of buckets, the algorithm transitions to a dynamic programming (DP) approach. Rather than tracking individual vertex permutations, the DP tracks the distribution of connected components of the remaining graph across the buckets. This "component-based counting" is a key optimization; since many different assignments of small components are functionally equivalent, the algorithm avoids redundant computations, drastically reducing the state space.

Results and Complexity

The algorithm achieves a worst-case running time of $O(1.9797^n)$. This result is significant as it surpasses the previous benchmarks for the problem:

  • Previous 2-approximation: $O^*(3^n)$
  • Previous 3-approximation: $O^*(2^n)$ (Cygan et al.)

The complexity analysis reveals that the "hardest" instances for this algorithm occur when the number of buckets $k$ is 7 or 8. For other values of $k$, the algorithm performs even faster. Notably, the algorithm is designed to use polynomial space, a rare feature for fast exponential algorithms, which often rely on exponential space (e.g., via inclusion-exclusion or large DP tables). This makes the algorithm more practical for implementation on standard hardware.

Conclusion

This paper provides a new upper bound for the 2-approximation of graph bandwidth, demonstrating that it is possible to break the $2^n$ barrier without requiring exponential memory. While the algorithm remains exponential and thus limited to graphs of moderate size, it narrows the gap in our understanding of the complexity of the Bandwidth problem.

Future research may focus on refining the techniques for the bottleneck cases ($k=7, 8$) to further reduce the exponent. Additionally, the authors suggest that under the Exponential Time Hypothesis (ETH), a subexponential time ($2^{o(n)}$) 2-approximation may be impossible, leaving a clear target for future lower-bound proofs.

Summary updated

BibTeX
@article{furer2013exponential,
  author = {Martin Fürer and Serge Gaspers and Shiva Prasad Kasiviswanathan},
  title = {{An Exponential Time 2-Approximation Algorithm for Bandwidth}},
  journal = {Theoretical Computer Science},
  year = {2013},
  doi = {10.1016/j.tcs.2013.03.024},
}
Figure