An exponential time 2-approximation algorithm for bandwidth. (English) Zbl 1273.68408
Chen, Jianer (ed.) et al., Parameterized and exact computation. 4th international workshop, IWPEC 2009, Copenhagen, Denmark, September 10–11, 2009. Revised selected papers. Berlin: Springer (ISBN 978-3-642-11268-3/pbk). Lecture Notes in Computer Science 5917, 173-184 (2009).
Summary: 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.
For the entire collection see [Zbl 1178.68005].
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.
For the entire collection see [Zbl 1178.68005].
MSC:
| 68W25 | Approximation algorithms |
| 05C78 | Graph labelling (graceful graphs, bandwidth, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
References:
| [1] | Amini, O., Fomin, F.V., Saurabh, S.: Counting Subgraphs via Homomorphisms. In: Proceedings of ICALP 2009, pp. 71-82 (2009) · Zbl 1247.05107 |
| [2] | 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) · Zbl 0947.90083 · doi:10.1016/S0304-3975(99)00181-4 |
| [3] | 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) · Zbl 1345.68152 |
| [4] | 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) · Zbl 1192.68313 |
| [5] | Cygan, M., Kowalik, L., Pilipczuk, M., Wykurz, M.: Exponential-time Approximation of Hard Problems, Technical Report abs/0810.4934, arXiv, CoRR (2008) · Zbl 1202.68482 |
| [6] | Cygan, M.; Pilipczuk, M.; Broersma, H.; Erlebach, T.; Friedetzky, T.; Paulusma, D., Faster exact bandwidth, Graph-Theoretic Concepts in Computer Science, 101-109 (2008), Heidelberg: Springer, Heidelberg · Zbl 1202.05135 · doi:10.1007/978-3-540-92248-3_10 |
| [7] | Cygan, M., Pilipczuk, M.: Even Faster Exact Bandwidth, Technical Report abs/0902.1661, arXiv, CoRR (2009) · Zbl 1295.68130 |
| [8] | Cygan, M., Pilipczuk, M.: Exact and approximate Bandwidth. In: Proceedings of ICALP 2009, pp. 304-315 (2009) · Zbl 1248.68371 |
| [9] | Dunagan, J.; Vempala, S. S.; Goemans, M. X.; Jansen, K.; Rolim, J. D.P.; Trevisan, L., On euclidean embeddings and bandwidth minimization, Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, 229-240 (2001), Heidelberg: Springer, Heidelberg · Zbl 1001.05045 · doi:10.1007/3-540-44666-4_26 |
| [10] | Feige, U., Approximating the Bandwidth via Volume Respecting Embeddings, J. Comput. Syst. Sci., 60, 3, 510-539 (2000) · Zbl 0958.68191 · doi:10.1006/jcss.1999.1682 |
| [11] | Feige, U.; Halldórsson, M. M., Coping with the NP-Hardness of the Graph Bandwidth Problem, Algorithm Theory - SWAT 2000, 10-19 (2000), Heidelberg: Springer, Heidelberg · Zbl 0966.68513 · doi:10.1007/3-540-44985-X_2 |
| [12] | Feige, U.; Talwar, K.; Chekuri, C.; Jansen, K.; Rolim, J. D.P.; Trevisan, L., Approximating the bandwidth of caterpillars, Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 62-73 (2005), Heidelberg: Springer, Heidelberg · Zbl 1142.05366 |
| [13] | Fürer, M., Gaspers, S., Kasiviswanathan, S.P.: An Exponential Time 2-Approximation Algorithm for Bandwidth, Technical Report abs/0906.1953, arXiv, CoRR (2009) · Zbl 1273.68408 |
| [14] | 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) · Zbl 0385.05048 · doi:10.1137/0134037 |
| [15] | Impagliazzo, R.; Paturi, R., On the Complexity of k-SAT, J. Comput. Syst. Sci., 62, 2, 367-375 (2001) · Zbl 0990.68079 · doi:10.1006/jcss.2000.1727 |
| [16] | Lee, J. R., Volume Distortion for subsets of Euclidean Spaces, Discrete Comput. Geom., 41, 4, 590-615 (2009) · Zbl 1341.68296 · doi:10.1007/s00454-009-9135-9 |
| [17] | 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) · Zbl 0624.68059 · doi:10.1137/0607057 |
| [18] | Monien, B., Sudborough, I.H.: Bandwidth Problems in Graphs. In: Proceedings of Allerton Conference on Communication, Control, and Computing 1980, pp. 650-659 (1980) |
| [19] | Papadimitriou, C., The NP-completeness of the Bandwidth Minimization Problem, Computing, 16, 263-270 (1976) · Zbl 0321.65019 · doi:10.1007/BF02280884 |
| [20] | Saxe, J., Dynamic Programming Algorithms for Recognizing Small-bandwidth Graphs in Polynomial Time, SIAM J. Alg. Disc. Meth., 1, 363-369 (1980) · Zbl 0496.68032 · doi:10.1137/0601042 |
| [21] | Unger, W.: The Complexity of the Approximation of the Bandwidth Problem. In: Proceedings of FOCS 1998, pp. 82-91 (1998) |
| [22] | Vassilevska, V., Williams, R., Woo, S.L.M.: Confronting Hardness using a Hybrid Approach. In: Proceedings of SODA 2006, pp. 1-10 (2006) · Zbl 1192.68381 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
