Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Parameterized Algorithms for Generalized Domination

  • Conference paper

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

  • 917Accesses

Abstract

We study the parameterized complexity of a generalization ofDominating Set problem, namely, theVector Dominating Set problem. Here, given an undirected graphG = (V,E), withV = {v1, ⋯ ,vn }, a vector\(\vec{l}=(l(v_1),\cdots, l(v_n))\) and an integer parameterk, the goal is to determine whether there exists a subsetD of at mostk vertices such that for every vertexv ∈ V ∖ D, at leastl(v) of its neighbors are inD. This problem encompasses the well studied problems –Vertex Cover (whenl(v) = d(v) for allv ∈ V, whered(v) is the degree of vertexv) andDominating Set (whenl(v) = 1 for allv ∈ V). WhileVertex Cover is known to be fixed parameter tractable,Dominating Set is known to beW[2]-complete. In this paper, we identify vectors based on several measures for which this generalized problem is fixed parameter tractable and W-hard. We also show that theVector Dominating Set is fixed parameter tractable for graphs of bounded degeneracy and for graphs excluding cycles of length four.

The work was done when the second and the third authors were at The Institute of Mathematical Sciences.

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

Access this chapter

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Alon, N., Gutner, S.: Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs. In: Lin, G. (ed.) COCOON. LNCS, vol. 4598, pp. 394–405. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  2. Cai, L., Juedes, D.: On the Existence of Subexponential Algorithms. Journal of Computer and System Sciences 67(4), 789–807 (2003)

    Article MATH MathSciNet  Google Scholar 

  3. Chen, J., Kanj, I.A., Xia, G.: Improved Parameterized Upper Bounds for Vertex Cover. In: Královič, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol. 4162, pp. 238–249. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  4. Demaine, E.D., Fomin, F.V., Hajiaghayi, M.T., Thilikos, D.M.: Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. Journal of ACM 52(6), 866–893 (2005)

    Article MathSciNet  Google Scholar 

  5. Diestel, R.: Graph Theory. Springer, Heidelberg (1997)

    MATH  Google Scholar 

  6. Downey, R.G., Fellows, M.R.: Threshold Dominating Sets and an Improved Characterization of W[2]. Theoretical Computer Science 209(1-2), 123–140 (1998)

    Article MATH MathSciNet  Google Scholar 

  7. Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)

    Google Scholar 

  8. Duh, R., Fürer, M.: Approximation of k-set cover by semi-local optimization. In: The Proceedings of STOC, pp. 256–264 (1997)

    Google Scholar 

  9. Edmonds, J.: Paths, trees and flowers. Canadian Journal of Mathematics 17, 449–467 (1965)

    MATH MathSciNet  Google Scholar 

  10. Feige, U.: A Threshold of lnn for Approximating Set Cover. Journal of ACM 45(4), 634–652 (1998)

    Article MATH MathSciNet  Google Scholar 

  11. Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)

    Google Scholar 

  12. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)

    MATH  Google Scholar 

  13. Gerlach, T., Harant, J.: A Note on Domination in Bipartite Graphs. Discuss. Math. Graph Theory 22, 229–231 (2002)

    MATH MathSciNet  Google Scholar 

  14. Johnson, D.S.: Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences 9(3), 256–278 (1974)

    Article MATH MathSciNet  Google Scholar 

  15. Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)

    MATH  Google Scholar 

  16. Raman, V., Saurabh, S.: Short Cycles make W-hard problems hard: FPT algorithms for W-hard Problems in Graphs with no short Cycles (to appear in Algorithmica)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. The Institute of Mathematical Sciences,  , C.I.T. Campus, Chennai, 600 113

    Venkatesh Raman

  2. Department of Informatics, University of Bergen, Bergen, Norway

    Saket Saurabh

  3. School of Computing, National University of Singapore1, Singapore, 117590

    Sriganesh Srihari

Authors
  1. Venkatesh Raman

    You can also search for this author inPubMed Google Scholar

  2. Saket Saurabh

    You can also search for this author inPubMed Google Scholar

  3. Sriganesh Srihari

    You can also search for this author inPubMed Google Scholar

Editor information

Boting Yang Ding-Zhu Du Cao An Wang

Rights and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Raman, V., Saurabh, S., Srihari, S. (2008). Parameterized Algorithms for Generalized Domination. In: Yang, B., Du, DZ., Wang, C.A. (eds) Combinatorial Optimization and Applications. COCOA 2008. Lecture Notes in Computer Science, vol 5165. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85097-7_11

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp