Skip to main content
SpringerLink
Log in

Parameterized Complexity for Domination Problems on Degenerate Graphs

  • Conference paper
Graph-Theoretic Concepts in Computer Science (WG 2008)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5344))

Included in the following conference series:

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 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)

    Article  MathSciNet  MATH  Google Scholar 

  2. 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)

    Chapter  Google Scholar 

  3. Amini, O., Fomin, F.V., Saurabh, S.: Parameterized algorithms for partial cover problems (submitted, 2008)

    Google Scholar 

  4. Bar-Ilan, J., Kortsarz, G., Peleg, D.: How to allocate network centers. J. Algorithms 15, 385–415 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  5. 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)

    Google Scholar 

  6. Cesati, M.: Perfect code is W[1]-complete. Inform. Process. Lett. 81, 163–168 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  7. Dawar, A., Grohe, M., Kreutzer, S.: Locally excluding a minor. In: LICS, pp. 270–279. IEEE Computer Society, Los Alamitos (2007)

    Google Scholar 

  8. 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)

    MathSciNet  MATH  Google Scholar 

  9. 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)

    Article  MathSciNet  MATH  Google Scholar 

  10. Demaine, E.D., Hajiaghayi1, M.T.: The bidimensionality theory and its algorithmic applications. The Computer Journal (2007)

    Google Scholar 

  11. Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness. I. Basic results. SIAM J. Comput., 24, 873–921 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  12. Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness. II. On completeness for W[1]. Theoret. Comput. Sci. 141, 109–131 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  13. Downey, R.G., Fellows, M.R.: Parameterized complexity, Monographs in Computer Science. Springer, New York (1999)

    Book  Google Scholar 

  14. Flum, J., Grohe, M.: Parameterized complexity theory, Texts in Theoretical Computer Science. EATCS Series. Springer, Berlin (2006)

    MATH  Google Scholar 

  15. Gabow, H.N., Myers, E.W.: Finding all spanning trees of directed and undirected graphs. SIAM J. Comput. 7, 280–287 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  16. Guo, J., Niedermeier, R., Wernicke, S.: Parameterized complexity of vertex cover variants. Theory Comput. Syst. 41, 501–520 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  17. 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)

    Chapter  Google Scholar 

  18. Kostochka, A.V.: The minimum Hadwiger number for graphs with a given mean degree of vertices, Metody Diskret., Analiz, pp. 37–58 (1982)

    Google Scholar 

  19. Thomason, A.: An extremal function for contractions of graphs. Math. Proc. Cambridge Philos. Soc. 95, 261–265 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  20. Thomason, A.: The extremal function for complete minors. J. Combin. Theory Ser. B 81, 318–338 (2001)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Informatics, University of Bergen, PB 7803, 5020, Bergen, Norway

    Petr A. Golovach & Yngve Villanger

Authors
  1. Petr A. Golovach
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yngve Villanger
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, Durham University, South Road, DH1 3LE, Durham, UK

    Hajo Broersma , Tom Friedetzky  & Daniel Paulusma ,  & 

  2. Department of Computer Science, University of Leicester, University Road, LE1 7RH, Leicester, UK

    Thomas Erlebach

Rights and permissions

Reprints 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)

Publish with us

Policies and ethics

Search

Navigation