×

Graph separators: A parameterized view. (English) Zbl 1091.68075

Summary: Graph separation is a well-known tool to make (hard) graph problems accessible to a divide-and-conquer approach. We show how to use graph separator theorems in combination with (linear) problem kernels in order to develop fixed parameter algorithms for many well-known NP-hard (planar) graph problems. We coin the key notion of glueable select\(\and\)verify graph problems and derive from that a prospective way to easily check whether a planar graph problem will allow for a fixed parameter algorithm of running time \(c^{\sqrt k}n^{O(1)}\) for constant \(c\). One of the main contributions of the paper is to exactly compute the base \(c\) of the exponential term and its dependence on the various parameters specified by the employed separator theorem and the underlying graph problem. We discuss several strategies to improve on the involved constant \(c\).

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C10 Planar graphs; geometric and topological aspects of graph theory
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J. Alber, H.L. Bodlaender, H. Fernau, R. Niedermeier, Fixed parameter algorithms for planar dominating set and related problems, in: Proceedings of the Seventh Scandinavian Workshop on Algorithm Theory SWAT’00, Lecture Notes in Computer Science, Vol. 1851, Springer, Berlin, 2000, pp. 97-110, long version to appear in Algorithmica.; J. Alber, H.L. Bodlaender, H. Fernau, R. Niedermeier, Fixed parameter algorithms for planar dominating set and related problems, in: Proceedings of the Seventh Scandinavian Workshop on Algorithm Theory SWAT’00, Lecture Notes in Computer Science, Vol. 1851, Springer, Berlin, 2000, pp. 97-110, long version to appear in Algorithmica. · Zbl 0966.68224
[2] J. Alber, H. Fan, M.R. Fellows, H. Fernau, R. Niedermeier, F. Rosamond, U. Stege, Refined search tree techniques for the planar dominating set; J. Alber, H. Fan, M.R. Fellows, H. Fernau, R. Niedermeier, F. Rosamond, U. Stege, Refined search tree techniques for the planar dominating set · Zbl 0999.68158
[3] J. Alber, M.R. Fellows, R. Niedermeier, Efficient data reduction for dominating set; J. Alber, M.R. Fellows, R. Niedermeier, Efficient data reduction for dominating set · Zbl 1078.68638
[4] J. Alber, H. Fernau, R. Niedermeier, Graph separators: a parameterized view, Technical Report WSI-2001-8, Universität Tübingen (Germany), Wilhelm-Schickard-Institut für Informatik, September 2001.; J. Alber, H. Fernau, R. Niedermeier, Graph separators: a parameterized view, Technical Report WSI-2001-8, Universität Tübingen (Germany), Wilhelm-Schickard-Institut für Informatik, September 2001. · Zbl 0991.68053
[5] J. Alber, H. Fernau, R. Niedermeier, Parameterized complexity: exponential speed-up for planar graph problems, Technical Report TR01-023, ECCC Reports, Trier, March 2001, Extended abstract in Proceedings of the 28th International Colloquium on Automata, Languages and Programming ICALP’01, Lecture Notes in Computer Science, Vol. 2076, Springer, Berlin, 2001, pp. 261-272.; J. Alber, H. Fernau, R. Niedermeier, Parameterized complexity: exponential speed-up for planar graph problems, Technical Report TR01-023, ECCC Reports, Trier, March 2001, Extended abstract in Proceedings of the 28th International Colloquium on Automata, Languages and Programming ICALP’01, Lecture Notes in Computer Science, Vol. 2076, Springer, Berlin, 2001, pp. 261-272. · Zbl 0987.68040
[6] Alber, J.; Gramm, J.; Niedermeier, R., Faster exact algorithms for hard problemsa parameterized point of view, Discrete Math., 229, 3-27 (2001) · Zbl 0973.68256
[7] Aleksandrov, L. G.; Djidjev, H. N., Linear algorithms for partitioning embedded graphs of bounded genus, SIAM J. Discrete Math., 9, 129-150 (1996) · Zbl 0847.05046
[8] N. Alon, P.D. Seymour, R. Thomas, A separator theorem for graphs with an excluded minor and its applications, in: Proceedings of the 22nd ACM Symposium on the Theory of Computing STOC’90, Baltimore, MD, May 14-16, 1990, pp. 293-299.; N. Alon, P.D. Seymour, R. Thomas, A separator theorem for graphs with an excluded minor and its applications, in: Proceedings of the 22nd ACM Symposium on the Theory of Computing STOC’90, Baltimore, MD, May 14-16, 1990, pp. 293-299.
[9] Alon, N.; Seymour, P. D.; Thomas, R., A separator theorem for nonplanar graphs, J. AMS, 3, 801-808 (1990) · Zbl 0747.05051
[10] Bar-Yehuda, R.; Even, S., A local-ratio theorem for approximating the weighted vertex cover problem, Ann. Discrete Math., 25, 27-46 (1985) · Zbl 0557.90072
[11] Bodlaender, H. L., A partial \(k\)-arboretum of graphs with bounded treewidth, Theoret. Comput. Sci., 209, 1-45 (1998) · Zbl 0912.68148
[12] Chen, J.; Kanj, I.; Jia, W., Vertex coverfurther observations and further improvements, J. Algorithms, 41, 280-301 (2001) · Zbl 1017.68087
[13] Chen, Z.-Z., Approximation algorithms for independent sets in map graphs, J. Algorithms, 41, 20-40 (2001) · Zbl 1002.68111
[14] Chen, Z.-Z.; Grigni, M.; Papadimitriou, C. H., Map graphs, J. ACM, 49, 127-138 (2002) · Zbl 1323.05039
[15] Djidjev, H. N., On the problem of partitioning planar graphs, SIAM J. Algebraic Discrete Methods, 3, 2, 229-240 (1982) · Zbl 0503.05057
[16] Djidjev, H. N., A separator theorem for graphs of fixed genus, Serdica, 11, 319-329 (1985)
[17] Djidjev, H. N.; Venkatesan, S. M., Reduced constants for simple cycle graph separation, Acta Inform., 34, 231-243 (1997) · Zbl 0865.05049
[18] Downey, R. G.; Fellows, M. R., Parameterized Complexity (1999), Springer: Springer Berlin · Zbl 0961.68533
[19] Eppstein, D., Diameter and treewidth in minor-closed graph families, Algorithmica, 27, 275-291 (2000) · Zbl 0963.05128
[20] M.R. Fellows, Parameterized complexity: the main ideas and some research frontiers, in: Proceedings of the 12th Annual International Symposium on Algorithms And Computation ISAAC’01, Lecture Notes in Computer Science, Vol. 2223, 2001, pp. 291-307.; M.R. Fellows, Parameterized complexity: the main ideas and some research frontiers, in: Proceedings of the 12th Annual International Symposium on Algorithms And Computation ISAAC’01, Lecture Notes in Computer Science, Vol. 2223, 2001, pp. 291-307. · Zbl 1077.68651
[21] Garey, M. R.; Johnson, D. S., Computers and Intractability (1979), Freeman: Freeman New York · Zbl 0411.68039
[22] M. Grohe, Local tree-width, excluded minors, and approximation algorithms, Combinatorica, 2001, to appear.; M. Grohe, Local tree-width, excluded minors, and approximation algorithms, Combinatorica, 2001, to appear.
[23] Lipton, R. J.; Tarjan, R. E., A separator theorem for planar graphs, SIAM J. Appl. Math., 36, 2, 177-189 (1979) · Zbl 0432.05022
[24] Lipton, R. J.; Tarjan, R. E., Applications of a planar separator theorem, SIAM J. Comput., 9, 3, 615-627 (1980) · Zbl 0456.68077
[25] Nemhauser, G. L.; Trotter, J. L.E., Vertex packingstructural properties and algorithms, Math. Programming, 8, 232-248 (1975) · Zbl 0314.90059
[26] R. Niedermeier, P. Rossmanith, Upper bounds for Vertex Cover further improved, in: Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science STACS’99, Lecture Notes in Computer Science, Vol. 1563, Springer, Berlin, 1999, pp. 561-570.; R. Niedermeier, P. Rossmanith, Upper bounds for Vertex Cover further improved, in: Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science STACS’99, Lecture Notes in Computer Science, Vol. 1563, Springer, Berlin, 1999, pp. 561-570. · Zbl 0921.05046
[27] R. Niedermeier, P. Rossmanith, On efficient fixed parameter algorithms for weighted vertex cover; R. Niedermeier, P. Rossmanith, On efficient fixed parameter algorithms for weighted vertex cover · Zbl 1044.68133
[28] Paschos, V. T., A survey of approximately optimal solutions to some covering and packing problems, ACM Comput. Surveys, 29, 2, 171-209 (1997)
[29] Ravi, S. S.; Hunt, H. B., An application of the planar separator theorem to counting problems, Inform. Process. Lett., 25, 6, 317-322 (1987) · Zbl 0653.68064
[30] N. Robertson, D.P. Sanders, P. Seymour, R. Thomas, Efficiently four-coloring planar graphs, in: Proceedings of the 28th ACM Symposium on the Theory of Computing STOC’96, 1996, pp. 571-575.; N. Robertson, D.P. Sanders, P. Seymour, R. Thomas, Efficiently four-coloring planar graphs, in: Proceedings of the 28th ACM Symposium on the Theory of Computing STOC’96, 1996, pp. 571-575. · Zbl 0917.05030
[31] Robson, J. M., Algorithms for maximum independent sets, J. Algorithms, 7, 3, 425-440 (1986) · Zbl 0637.68080
[32] D.A. Spielman, S.-H. Teng, Disk packings and planar separators, in: SCG 96: 12th Annual ACM Symposium on Computational Geometry, 1996, pp. 349-358.; D.A. Spielman, S.-H. Teng, Disk packings and planar separators, in: SCG 96: 12th Annual ACM Symposium on Computational Geometry, 1996, pp. 349-358.
[33] Telle, J. A., Complexity of domination-type problems in graphs, Nordic J. Comput., 1, 157-171 (1994)
[34] J.A. Telle, A. Proskurowski, Practical algorithms on partial \(k\); J.A. Telle, A. Proskurowski, Practical algorithms on partial \(k\)
[35] Telle, J. A.; Proskurowski, A., Algorithms for vertex partitioning problems on partial \(k\)-trees, SIAM J. Discrete Math., 10, 4, 529-550 (1997) · Zbl 0885.68118
[36] Yannakakis, M.; Gavril, F., Edge dominating sets in graphs, SIAM J. Appl. Math., 38, 3, 364-372 (1980) · Zbl 0455.05047
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.