Abstract
The bandwidth of a graph G on n vertices is the minimum b such that the vertices of G can be labeled from 1 to n such that the labels of every pair of adjacent vertices differ by at most b.
In this paper, we present a 2-approximation algorithm for the Bandwidth problem that takes worst-case \(\mathcal{O}(1.9797^n)\) \(= \mathcal{O}(3^{0.6217 n})\) time and uses polynomial space. This improves both the previous best 2- and 3-approximation algorithms of Cygan et al. which have an \(\mathcal{O}^*(3^n)\) and \(\mathcal{O}^*(2^n)\) worst-case time bounds, respectively. Our algorithm is based on constructing bucket decompositions of the input graph. A bucket decomposition partitions the vertex set of a graph into ordered sets (called buckets) of (almost) equal sizes such that all edges are either incident on vertices in the same bucket or on vertices in two consecutive buckets. The idea is to find the smallest bucket size for which there exists a bucket decomposition. The algorithm uses a simple divide-and-conquer strategy along with dynamic programming to achieve this improved time bound.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Amini, O., Fomin, F.V., Saurabh, S.: Counting Subgraphs via Homomorphisms. In: Proceedings of ICALP 2009, pp. 71–82 (2009)
Blum, A., Konjevod, G., Ravi, R., Vempala, S.: Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering problems. Theor. Comput. Sci. 235(1), 25–42 (2000)
Bodlaender, H.L., Fellows, M.R., Hallett, M.T.: Beyond NP-completeness for Problems of Bounded Width: Hardness for the W-hierarchy. In: Proceedings of STOC 1994, pp. 449–458 (1994)
Chen, J., Huang, X., Kanj, I.A., Xia, G.: Linear FPT Reductions and Computational Lower Bounds. In: Proceedings of STOC 2004, pp. 212–221 (2004)
Cygan, M., Kowalik, L., Pilipczuk, M., Wykurz, M.: Exponential-time Approximation of Hard Problems, Technical Report abs/0810.4934, arXiv, CoRR (2008)
Cygan, M., Pilipczuk, M.: Faster exact bandwidth. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol. 5344, pp. 101–109. Springer, Heidelberg (2008)
Cygan, M., Pilipczuk, M.: Even Faster Exact Bandwidth, Technical Report abs/0902.1661, arXiv, CoRR (2009)
Cygan, M., Pilipczuk, M.: Exact and approximate Bandwidth. In: Proceedings of ICALP 2009, pp. 304–315 (2009)
Dunagan, J., Vempala, S.S.: On euclidean embeddings and bandwidth minimization. In: Goemans, M.X., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) RANDOM 2001 and APPROX 2001. LNCS, vol. 2129, pp. 229–240. Springer, Heidelberg (2001)
Feige, U.: Approximating the Bandwidth via Volume Respecting Embeddings. J. Comput. Syst. Sci. 60(3), 510–539 (2000)
Feige, U.: Coping with the NP-Hardness of the Graph Bandwidth Problem. In: Halldórsson, M.M. (ed.) SWAT 2000. LNCS, vol. 1851, pp. 10–19. Springer, Heidelberg (2000)
Feige, U., Talwar, K.: Approximating the bandwidth of caterpillars. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol. 3624, pp. 62–73. Springer, Heidelberg (2005)
Fürer, M., Gaspers, S., Kasiviswanathan, S.P.: An Exponential Time 2-Approximation Algorithm for Bandwidth, Technical Report abs/0906.1953, arXiv, CoRR (2009)
Garey, M.R., Graham, R.L., Johnson, D.S., Knuth, D.E.: Complexity Results for Bandwidth Minimization. SIAM J. Appl. Math. 34(3), 477–495 (1978)
Impagliazzo, R., Paturi, R.: On the Complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367–375 (2001)
Lee, J.R.: Volume Distortion for subsets of Euclidean Spaces. Discrete Comput. Geom. 41(4), 590–615 (2009)
Monien, B.: The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-complete. SIAM J. Alg. Disc. Meth. 7(4), 505–512 (1986)
Monien, B., Sudborough, I.H.: Bandwidth Problems in Graphs. In: Proceedings of Allerton Conference on Communication, Control, and Computing 1980, pp. 650–659 (1980)
Papadimitriou, C.: The NP-completeness of the Bandwidth Minimization Problem. Computing 16, 263–270 (1976)
Saxe, J.: Dynamic Programming Algorithms for Recognizing Small-bandwidth Graphs in Polynomial Time. SIAM J. Alg. Disc. Meth. 1, 363–369 (1980)
Unger, W.: The Complexity of the Approximation of the Bandwidth Problem. In: Proceedings of FOCS 1998, pp. 82–91 (1998)
Vassilevska, V., Williams, R., Woo, S.L.M.: Confronting Hardness using a Hybrid Approach. In: Proceedings of SODA 2006, pp. 1–10 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fürer, M., Gaspers, S., Kasiviswanathan, S.P. (2009). An Exponential Time 2-Approximation Algorithm for Bandwidth. In: Chen, J., Fomin, F.V. (eds) Parameterized and Exact Computation. IWPEC 2009. Lecture Notes in Computer Science, vol 5917. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11269-0_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-11269-0_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11268-3
Online ISBN: 978-3-642-11269-0
eBook Packages: Computer ScienceComputer Science (R0)