iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.4230/LIPIcs.IPEC.2020.9
New Algorithms for Mixed Dominating Set
Document Open Access Logo

New Algorithms for Mixed Dominating Set

Authors Louis Dublois, Michael Lampis, Vangelis Th. Paschos

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2020.9.pdf
  • Filesize: 0.52 MB
  • 17 pages

Document Identifiers

Author Details

Louis Dublois
  • Université Paris-Dauphine, PSL University, CNRS, LAMSADE, Paris, France
Michael Lampis
  • Université Paris-Dauphine, PSL University, CNRS, LAMSADE, Paris, France
Vangelis Th. Paschos
  • Université Paris-Dauphine, PSL University, CNRS, LAMSADE, Paris, France

Cite AsGet BibTex

Louis Dublois, Michael Lampis, and Vangelis Th. Paschos. New Algorithms for Mixed Dominating Set. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.IPEC.2020.9

Abstract

A mixed dominating set is a set of vertices and edges that dominates all vertices and edges of a graph. We study the complexity of exact and parameterized algorithms for MDS, resolving some open questions. In particular, we settle the problem’s complexity parameterized by treewidth and pathwidth by giving an algorithm running in time O^*(5^{tw}) (improving the current best O^*(6^{tw})), and a lower bound showing that our algorithm cannot be improved under the SETH, even if parameterized by pathwidth (improving a lower bound of O^*((2-ε)^{pw})). Furthermore, by using a simple but so far overlooked observation on the structure of minimal solutions, we obtain branching algorithms which improve the best known FPT algorithm for this problem, from O^*(4.172^k) to O^*(3.510^k), and the best known exact algorithm, from O^*(2ⁿ) and exponential space, to O^*(1.912ⁿ) and polynomial space.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • FPT Algorithms
  • Exact Algorithms
  • Mixed Domination

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Yousef Alavi, M. Behzad, Linda M. Lesniak-Foster, and E. A. Nordhaus. Total matchings and total coverings of graphs. Journal of Graph Theory, 1(2):135-140, 1977. Google Scholar
  2. Yousef Alavi, Jiuqiang Liu, Jianfang Wang, and Zhongfu Zhang. On total covers of graphs. Discrete Mathematics, 100(1-3):229-233, 1992. Google Scholar
  3. Glencora Borradaile and Hung Le. Optimal dynamic program for r-domination problems over tree decompositions. In IPEC, volume 63 of LIPIcs, pages 8:1-8:23, 2016. Google Scholar
  4. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  5. Szymon Dudycz, Mateusz Lewandowski, and Jan Marcinkowski. Tight approximation ratio for minimum maximal matching. In IPCO, volume 11480 of LNCS. Springer, 2019. Google Scholar
  6. Paul Erdös and Amram Meir. On total matching numbers and total covering numbers of complementary graphs. Discrete Mathematics, 19(3):229-233, 1977. Google Scholar
  7. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Intractability of clique-width parameterizations. SIAM J. Comput., 39(5):1941-1956, 2010. Google Scholar
  8. Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Yota Otachi, and Florian Sikora. Parameterized orientable deletion. In SWAT, volume 101 of LIPIcs, pages 24:1-24:13, 2018. Google Scholar
  9. Pooya Hatami. An approximation algorithm for the total covering problem. Discussiones Mathematicae Graph Theory, 27(3):553-558, 2007. Google Scholar
  10. Teresa W. Haynes, Stephen T. Hedetniemi, and Peter J. Slater. Fundamentals of domination in graphs, volume 208 of Pure and applied mathematics. Dekker, 1998. Google Scholar
  11. Lars Jaffke and Bart M. P. Jansen. Fine-grained parameterized complexity analysis of graph coloring problems. In CIAC, volume 10236 of LNCS, pages 345-356, 2017. Google Scholar
  12. Pallavi Jain, M. Jayakrishnan, Fahad Panolan, and Abhishek Sahu. Mixed dominating set: A parameterized perspective. In WG, volume 10520 of LNCS, pages 330-343. Springer, 2017. Google Scholar
  13. Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos. Structurally parameterized d-scattered set. In WG, volume 11159 of LNCS, pages 292-305. Springer, 2018. Google Scholar
  14. Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos. Structural parameters, tight bounds, and approximation for (k, r)-center. Discr. Applied Math., 264:90-117, 2019. Google Scholar
  15. Michael Lampis. Finer tight bounds for coloring on clique-width. In ICALP, volume 107 of LIPIcs, pages 86:1-86:14, 2018. Google Scholar
  16. James K. Lan and Gerard Jennhwa Chang. On the mixed domination problem in graphs. TCS, 476:84-93, 2013. Google Scholar
  17. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Known algorithms on graphs of bounded treewidth are probably optimal. ACM Trans. Algorithms, 14(2):13:1-13:30, 2018. Google Scholar
  18. Jayakrishnan Madathil, Fahad Panolan, Abhishek Sahu, and Saket Saurabh. On the complexity of mixed dominating set. In CSR, volume 11532 of LNCS, pages 262-274. Springer, 2019. Google Scholar
  19. Aniket Majumdar. Neighborhood hypergraphs: A framework for covering and packing parameters in graphs. PhD thesis, Clemson University, 1993. Google Scholar
  20. David Manlove. On the algorithmic complexity of twelve covering and independence parameters of graphs. Discrete Applied Mathematics, 91(1-3):155-175, 1999. Google Scholar
  21. Amram Meir. On total covering and matching of graphs. JCTS B, 24(2):164-168, 1978. Google Scholar
  22. John W Moon and Leo Moser. On cliques in graphs. Israel j. of Math., 3(1):23-28, 1965. Google Scholar
  23. Uri N. Peled and Feng Sun. Total matchings and total coverings of threshold graphs. Discrete Applied Mathematics, 49(1-3):325-330, 1994. Google Scholar
  24. M. Rajaati, Mohammad Reza Hooshmandasl, Michael J. Dinneen, and Ali Shakiba. On fixed-parameter tractability of the mixed domination problem for graphs with bounded tree-width. Discrete Mathematics & Theoretical Computer Science, 20(2), 2018. Google Scholar
  25. M. Rajaati, P. Sharifani, Ali Shakiba, Mohammad Reza Hooshmandasl, and Michael J. Dinneen. An efficient algorithm for mixed domination on generalized series-parallel graphs. CoRR, abs/1708.00240, 2017. URL: http://arxiv.org/abs/1708.00240.
  26. Mingyu Xiao and Zimo Sheng. Improved parameterized algorithms for mixed domination. In AAIM, volume 11640 of LNCS, pages 304-315. Springer, 2019. Google Scholar
  27. Yancai Zhao, Liying Kang, and Moo Young Sohn. The algorithmic complexity of mixed domination in graphs. Theor. Comput. Sci., 412(22):2387-2392, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact