Abstract
We present an algorithm for computing the domination number of a planar graph that uses \( O\left( {c^{\sqrt k } n} \right) \) time, where k is the domination number of the given planar input graph and \( c = 3^{6\sqrt {34} } \) . To obtain this result, we show that the treewidth of a planar graph with domination number k is \( O\left( {\sqrt k } \right) \) , and that such a tree decomposition can be found in \( O\left( {\sqrt {kn} } \right) \) time. The same technique can be used to show that the disk dimension problem (find a minimum set of faces that cover all vertices of a given plane graph) can be solved in \( O\left( {c_1^{\sqrt {k_n } } } \right) \) time for \( c_1 = 2^{6\sqrt {34} } \) . Similar results can be obtained for some variants of {updominating set}, e.g., INDEPENDENT DOMINATING SET.
Work supported by the DFG-research project PEAL (Parameterized complexity and Exact ALgorithms), NI 369/1-1.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
B. S. Baker, Approximation algorithms for NP-complete problems on planar graphs, Journal of the ACM 41:153–180, 1994.
D. Bienstock and C. L. Monma, On the complexity of covering vertices by faces in a planar graph. SIAM J. Comput. 17(1):53–76, 1988.
H. L. Bodlaender, A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25:1305–1317, 1996.
H. L. Bodlaender, Treewidth: Algorithmic techniques and results. In Proceedings 22nd MFCS’97, Springer-Verlag LNCS 1295, pp. 19–36, 1997.
H. L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth. Theor.Comp. Sci. 209:1–45, 1998.
A. Brandstädt, V. B. Le, and J. P. Spinrad, Graph Classes: a Survey, SIAM Monographs on Discrete Mathematics and Applications, 1999.
H. J. Broersma, T. Kloks, D. Kratsch, and H. Müller, Independent sets in AT-free graphs, In Proceedings ICALP’97, Springer-Verlag LNCS 1256, pp. 760–770, 1997.
M. S. Chang, Efficient algorithms for the domination problem on interval and circular arc graphs, SIAM J. Comput. 27:1671–1694, 1998.
J. Chen, I. Kanj, and W. Jia, Vertex cover: further observations and further improvements. In Proceedings 25th WG, Springer-Verlag LNCS 1665, pp. 313–324, 1999.
D. G. Corneil and L. K. Stewart, Dominating sets in perfect graphs, Discrete Mathematics 86, (1990), 145–164.
P. Crescenzi and V. Kann, A compendium of NP optimization problems. Available at http://www.nada.kth.se/theory/problemlist.html, August 1998.
M. Damian-Iordache and S.V. Pemmaraju, A (2 + ε)-approximation scheme for minimum domination on circle graphs. In Proceedings 11th ACM-SIAM SODA 2000, pp. 672–679.
R. G. Downey and M. R. Fellows, Parameterized computational feasibility. In P. Clote, J. Remmel (eds.): Feasible Mathematics II, pp. 219–244. Birkhäuser, 1995.
R. G. Downey and M. R. Fellows, Parameterized Complexity, Springer-Verlag, 1999.
R. D. Dutton and R. C. Brigham, Domination in claw-free graphs, Congr. Num. 132: 69–75, 1998.
M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, 1979.
T. W. Haynes, S. T. Hedetniemi, and P. J. Slater (eds.), Domination in graphs, Marcel Dekker, 1998.
M. A. Henning, Domination in graphs, A survey, Congr. Num. 116:139–179, 1996.
D. S. Hochbaum (ed.), Approximation algorithms for NP-hard problems. PWS Publishing Company, 1997.
A. Kanevsky, Finding all minimum-size separating vertex sets in a graph, Networks 23: 533–541, 1993.
J. van Leeuwen, Graph Algorithms, In Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity Theory, North Holland, 1990.
H. Müller and A. Brandstädt, The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs, Theor. Comp. Sci. 53:257–265, 1987.
R. Niedermeier and P. Rossmanith. Upper bounds for Vertex Cover further improved. In Proceedings 16th STACS, Springer-Verlag LNCS 1563, pp. 561–570, 1999.
C. H. Papadimitriou, Computational Complexity. Addison-Wesley, 1994.
R. C. Read, Prospects for graph theory algorithms. Ann. Discr. Math. 55:201–210, 1993.
J. A. Telle, Complexity of domination-type problems in graphs, Nordic J. Comput. 1:157–171, 1994.
J. A. Telle and A. Proskurowski, Algorithms for vertex partitioning problems on partial k-trees, SI AM J. Discr. Math. 10(4):529–550, 1997.
Author information
Authors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Alber, J., Bodlaender, H.L., Fernau, H., Niedermeier, R. (2000). Fixed Parameter Algorithms for Planar Dominating Set and Related Problems. In: Algorithm Theory - SWAT 2000. SWAT 2000. Lecture Notes in Computer Science, vol 1851. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44985-X_10
Download citation
DOI: https://doi.org/10.1007/3-540-44985-X_10
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67690-4
Online ISBN: 978-3-540-44985-0
eBook Packages: Springer Book Archive