Abstract
Domination problems are one of the classical types of problems in computer science. These problems are considered in many different versions and on different classes of graphs. We explore the boundary between fixed-parameter tractable and W-hard problems on sparse graphs. More precisely, we expand the list of domination problems which are fixed-parameter tractable(FPT) for degenerate graphs by proving that Connected k -Dominating set and k -Dominating threshold set are FPT. From the other side we prove that there are domination problems which are difficult (W[1] or W[2]-hard) for this graph class. The Partial k -dominating set and (k,r)-Center for r ≥ 2 are examples of such problems. It is also remarked that domination problems become difficult for graphs of bounded average degree.
Supported by Norwegian Research Council.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
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, 461–493 (2002)
Alon, N., Gutner, S.: Linear time algorithms for finding a dominating set of fixed size in degenerated graphs. In: Lin, G. (ed.) COCOON 2007. LNCS, vol. 4598, pp. 394–405. Springer, Heidelberg (2007)
Amini, O., Fomin, F.V., Saurabh, S.: Parameterized algorithms for partial cover problems (submitted, 2008)
Bar-Ilan, J., Kortsarz, G., Peleg, D.: How to allocate network centers. J. Algorithms 15, 385–415 (1993)
Cai, L., Kloks, T.: Parameterized tractability of some (efficient) Y -domination variants for planar graphs and t-degenerate graphs. In: International Computer Symposium (ICS), Taiwan (2000)
Cesati, M.: Perfect code is W[1]-complete. Inform. Process. Lett. 81, 163–168 (2002)
Dawar, A., Grohe, M., Kreutzer, S.: Locally excluding a minor. In: LICS, pp. 270–279. IEEE Computer Society, Los Alamitos (2007)
Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Fixed-parameter algorithms for (k,r)-center in planar graphs and map graphs, ACM Trans. Algorithms 1, 33–47 (2005)
Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM 52, 866–893 (2005) (electronic)
Demaine, E.D., Hajiaghayi1, M.T.: The bidimensionality theory and its algorithmic applications. The Computer Journal (2007)
Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness. I. Basic results. SIAM J. Comput., 24, 873–921 (1995)
Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness. II. On completeness for W[1]. Theoret. Comput. Sci. 141, 109–131 (1995)
Downey, R.G., Fellows, M.R.: Parameterized complexity, Monographs in Computer Science. Springer, New York (1999)
Flum, J., Grohe, M.: Parameterized complexity theory, Texts in Theoretical Computer Science. EATCS Series. Springer, Berlin (2006)
Gabow, H.N., Myers, E.W.: Finding all spanning trees of directed and undirected graphs. SIAM J. Comput. 7, 280–287 (1978)
Guo, J., Niedermeier, R., Wernicke, S.: Parameterized complexity of vertex cover variants. Theory Comput. Syst. 41, 501–520 (2007)
Kneis, J., Mölle, D., Rossmanith, P.: Partial vs. complete domination: t-dominating set. In: van Leeuwen, J., Italiano, G.F., van der Hoek, W., Meinel, C., Sack, H., Plášil, F. (eds.) SOFSEM 2007. LNCS, vol. 4362, pp. 367–376. Springer, Heidelberg (2007)
Kostochka, A.V.: The minimum Hadwiger number for graphs with a given mean degree of vertices, Metody Diskret., Analiz, pp. 37–58 (1982)
Thomason, A.: An extremal function for contractions of graphs. Math. Proc. Cambridge Philos. Soc. 95, 261–265 (1984)
Thomason, A.: The extremal function for complete minors. J. Combin. Theory Ser. B 81, 318–338 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Golovach, P.A., Villanger, Y. (2008). Parameterized Complexity for Domination Problems on Degenerate Graphs. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds) Graph-Theoretic Concepts in Computer Science. WG 2008. Lecture Notes in Computer Science, vol 5344. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-92248-3_18
Download citation
DOI: https://doi.org/10.1007/978-3-540-92248-3_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-92247-6
Online ISBN: 978-3-540-92248-3
eBook Packages: Computer ScienceComputer Science (R0)