×

zbMATH — the first resource for mathematics

A refined search tree technique for dominating set on planar graphs. (English) Zbl 1101.68712
Summary: We establish a refined search tree technique for the parameterized DOMINATING SET problem on planar graphs. Here, we are given an undirected graph and we ask for a set of at most k vertices such that every other vertex has at least one neighbor in this set. We describe algorithms with running times \(O(8^{k}n)\) and \(O(8^{k}k+n^{3})\), where \(n\) is the number of vertices in the graph, based on bounded search trees. We describe a set of polynomial time data-reduction rules for a more general ”annotated” problem on black/white graphs that asks for a set of \(k\) vertices (black or white) that dominate all the black vertices. An intricate argument based on the Euler formula then establishes an efficient branching strategy for reduced inputs to this problem. In addition, we give a family examples showing that the bound of the branching theorem is optimal with respect to our reduction rules. Our final search tree algorithm is easy to implement; its analysis, however, is involved.

MSC:
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] J. Alber, Exact Algorithms for NP-hard Problems on Networks: Design, Analysis, and Implementation, Ph.D. Thesis, Universität Tübingen, Germany, January 2003.
[2] Alber, J.; Betzler, N.; Niedermeier, R., Experiments on data reduction for optimal domination in networks, (), 1-6
[3] Alber, J.; Bodlaender, H.L.; Fernau, H.; Kloks, T.; Niedermeier, R., Fixed parameter algorithms for dominating set and related problems on planar graphs, Algorithmica, 33, 4, 461-493, (2002) · Zbl 1016.68055
[4] Alber, J.; Fellows, M.R.; Niedermeier, R., Polynomial-time data reduction for dominating set, J. ACM, 51, 3, 363-384, (2004) · Zbl 1192.68337
[5] Alber, J.; Fernau, H.; Niedermeier, R., Graph separatorsa parameterized view, J. comput. system sci., 67, 4, 808-832, (2003) · Zbl 1091.68075
[6] Alber, J.; Fernau, H.; Niedermeier, R., Parameterized complexity: exponential speedup for planar graph problems, J. algorithms, 52, 1, 26-56, (2004) · Zbl 1085.68102
[7] Baker, B.S., Approximation algorithms for NP-complete problems on planar graphs, J. ACM, 41, 1, 153-180, (1994) · Zbl 0807.68067
[8] Chen, J.; Kanj, I.A.; Jia, W., Vertex coverfurther observations and further improvements, J. algorithms, 41, 280-301, (2001) · Zbl 1017.68087
[9] E.D. Demaine, F.V. Fomin, M. Taghi Hajiaghayi, D.M. Thilikos, Fixed-parameter algorithms for the \((k, r)\)-center in planar graphs and map graphs, in: 30th International Colloquium on Automata, Languages and Programming 2003, Lecture Notes in Computer Science, vol. 2719, Springer, Berlin, 2003, pp. 829-844. · Zbl 1039.68093
[10] E.D. Demaine, F.V. Fomin, M. Taghi Hajiaghayi, D.M. Thilikos, Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs. 15th ACM-SIAM Symposium on Discrete Algorithms 2004, 2004, pp. 830-839. · Zbl 1318.05076
[11] E.D. Demaine, F.V. Fomin, M. Taghi Hajiaghayi, D.M. Thilikos, Bidimensional parameters and local treewidth. Latin American Theoretical Informatics 2004, Lecture Notes in Computer Science, vol. 2976, Springer, Berlin, 2004, pp. 109-118. (Long version to appear in SIAM J. Disc. Math.) · Zbl 1196.68169
[12] E.D. Demaine, M. Taghi Hajiaghayi, D.M. Thilikos, Exponential speedup of fixed-parameter algorithms on \(K_{3, 3}\)-minor-free or \(K_5\)-minor-free graphs, in: 13th Annual International Symposium on Algorithms and Computation 2002, Lecture Notes in Computer Science, vol. 2518, Springer, Berlin, 2002, pp. 262-273. · Zbl 1020.05063
[13] Diestel, R., Graph theory, (2000), Springer Berlin · Zbl 0945.05002
[14] Downey, R.G.; Fellows, M.R., Parameterized computational feasibility, (), 219-244 · Zbl 0834.68046
[15] Downey, R.G.; Fellows, M.R., Parameterized complexity, (1999), Springer Berlin · Zbl 0914.68076
[16] R.G. Downey, M.R. Fellows, U. Stege, Parameterized complexity: a framework for systematically confronting computational intractability. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 49, 1999, pp. 49-99. · Zbl 0935.68046
[17] J. Ellis, H. Fan, M.R. Fellows, The dominating set problem is fixed parameter tractable for graphs of bounded genus, J. Algorithms 52 (2) (2004) 152-168. · Zbl 1072.68079
[18] Feige, U., A threshold of \(\ln n\) for approximating set cover, J. ACM, 45, 634-652, (1998) · Zbl 1065.68573
[19] Fomin, F.V.; Thilikos, D.T., Dominating sets in planar graphsbranch-width and exponential speed-up, (), 168-177 · Zbl 1094.68610
[20] F.V. Fomin, D.T. Thilikos, Dominating sets and local treewidth, in: 11th European Symposium on Algorithms 2003, Lecture Notes in Computer Science, vol. 2832, Springer, Berlin, 2003, pp. 221-229. · Zbl 1266.05164
[21] F.V. Fomin, D.T. Thilikos, A simple and fast approach for solving problems on planar graphs, 21st International Symposium on Theoretical Aspects of Computer Science 2004, Lecture Notes in Computer Science, vol. 2996, Springer, Berlin, 2004, pp. 56-67. · Zbl 1122.68480
[22] Garey, M.R.; Johnson, D.S., Computers and intractabilitya guide to the theory of NP-completeness, (1979), Freeman New York
[23] Haynes, T.W.; Hedetniemi, S.T.; Slater, P.J., Fundamentals of domination in graphs, () · Zbl 1103.05087
[24] T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Domination in Graphs, Monographs and Textbooks in Pure and Applied Mathematics, vol. 209, Marcel Dekker, New York, 1998.
[25] R. Niedermeier, P. Rossmanith, Upper bounds for vertex cover further improved, in: 16th International Symposium on Theoretical Aspects of Computer Science STACS 1999, Lecture Notes in Computer Science, vol. 1563, Springer, Berlin, 1999, pp. 561-570. · Zbl 0921.05046
[26] Niedermeier, R.; Rossmanith, P., A general method to speed up fixed-parameter-tractable algorithms, Inform. process. lett., 73, 3-4, 125-129, (2000) · Zbl 1014.68064
[27] Niedermeier, R.; Rossmanith, P., On efficient fixed-parameter algorithms for weighted vertex cover, J. algorithms, 47, 2, 63-77, (2003) · Zbl 1046.68058
[28] West, D.B., Introduction to graph theory, (2001), Prentice-Hall Englewood Cliffs, NJ
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.