Minimum bandwidth problem is to a find an ordering of graph nodes on integer lin
ID: 646418 • Letter: M
Question
Minimum bandwidth problem is to a find an ordering of graph nodes on integer
line that minimizes the largest distance between any two adjacent nodes.
The decision problem is NP-complete even for binary trees. Complexity Results
for Bandwidth Minimization. Garey, Graham, Johnson and Knuth, SIAM J. Appl.
Math., Vol. 34, No.3, 1978.
What is the best known efficient approximability result for computing minimum
bandwidth on binary trees? What is best known conditional hardness of
approximation result?
Explanation / Answer
Blache et. al, On Approximation Intractability of the Bandwidth Problem, 1997
confirms there is no PTAS for the problem unless P=NP, even for (binary) trees.
Unger W, The Complexity of the Approximation of the Bandwidth Problem, 1998
show that for any constant k?N there is no polynomial time approximation
algorithm with an approximation factor of k. So, unfortunately there's no PTAS
nor APX for the problem.
However, for some types of graphs, the problem can be solved or approximated in
polynomial time. For a recent survey, see Petit J., Addenda to the Survey of
Layout Problems, 2011. In the survey, see Tables 3, 4 and 8. The survey also
gives a nice list of references if you want to dig in deeper to some direction.
This is an more updated version of the older survey by Diaz et al., A survey of
Graph Layout Problems, 2002.
In case you are interested in the exact algorithm as well, I think currently
the fastest one is given by Cygan M. and Pilipczuk M., Even Faster Exact
Bandwidth, 2012. The algorithm runs in O(4.83n) time.