Document Open Access Logo

Dominating Set in Weakly Closed Graphs is Fixed Parameter Tractable

Authors Daniel Lokshtanov, Vaishali Surianarayanan

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2021.29.pdf
  • Filesize: 0.82 MB
  • 17 pages

Document Identifiers

Author Details

Daniel Lokshtanov
  • University of California Santa Barbara, CA, USA
Vaishali Surianarayanan
  • University of California Santa Barbara, CA, USA

Funding

The authors are supported by BSF award 2018302 and NSF award CCF-2008838.

Acknowledgements

We thank Saket Saurabh for insightful feedback on the manuscript.

Cite AsGet BibTex

Daniel Lokshtanov and Vaishali Surianarayanan. Dominating Set in Weakly Closed Graphs is Fixed Parameter Tractable. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.FSTTCS.2021.29

Abstract

In the Dominating Set problem the input is a graph G and an integer k, the task is to determine whether there exists a vertex set S of size at most k so that every vertex not in S has at least one neighbor in S. We consider the parameterized complexity of the Dominating Set problem, parameterized by the solution size k, and the weak closure of the input graph G. Weak closure of graphs was recently introduced by Fox et al. [SIAM J. Comp. 2020 ] and captures sparseness and triadic closure properties found in real world graphs. A graph G is weakly c-closed if for every induced subgraph G' of G, there exists a vertex v ∈ V(G') such that every vertex u in V(G') which is non-adjacent to v has less than c common neighbors with v. The weak closure of G is the smallest integer γ such that G is weakly γ-closed. We give an algorithm for Dominating Set with running time k^O(γ² k³) n^O(1), resolving an open problem of Koana et al. [ISAAC 2020]. One of the ingredients of our algorithm is a proof that the VC-dimension of (the set system defined by the closed neighborhoods of the vertices of) a weakly γ-closed graph is upper bounded by 6γ. This result may find further applications in the study of weakly closed graphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
Keywords
  • Dominating Set
  • Weakly Closed Graphs
  • FPT
  • Domination Cores
  • VC-dimension

Metrics

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

References

  1. Jochen Alber, Hans L. Bodlaender, Henning Fernau, Ton Kloks, and Rolf Niedermeier. Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs. Algorithmica, 33(4):461-493, 2002. Google Scholar
  2. Jochen Alber, Michael R. Fellows, and Rolf Niedermeier. Polynomial-time data reduction for dominating set. J. ACM, 51(3):363-384, 2004. Google Scholar
  3. Noga Alon and Shai Gutner. Linear time algorithms for finding a dominating set of fixed size in degenerated graphs. Algorithmica, 54(4):544-556, 2009. Google Scholar
  4. Noga Alon and Vojtěch Rödl. Asymptotically tight bounds for some multicolored ramsey numbers. Google Scholar
  5. Hervé Brönnimann and Michael T. Goodrich. Almost optimal set covers in finite vc-dimension. Discret. Comput. Geom., 14(4):463-479, 1995. Google Scholar
  6. Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca Trevisan. From gap-eth to fpt-inapproximability: Clique, dominating set, and more. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 743-754. IEEE Computer Society, 2017. Google Scholar
  7. Jianer Chen, Henning Fernau, Iyad A. Kanj, and Ge Xia. Parametric duality and kernelization: Lower bounds and upper bounds on kernel size. SIAM J. Comput., 37(4):1077-1106, 2007. Google Scholar
  8. Yijia Chen and Bingkai Lin. The constant inapproximability of the parameterized dominating set problem. SIAM J. Comput., 48(2):513-533, 2019. Google Scholar
  9. 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
  10. Anuj Dawar and Stephan Kreutzer. Domination problems in nowhere-dense classes. In Ravi Kannan and K. Narayan Kumar, editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009, December 15-17, 2009, IIT Kanpur, India, volume 4 of LIPIcs, pages 157-168. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2009. Google Scholar
  11. Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thilikos. Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM, 52(6):866-893, 2005. Google Scholar
  12. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  13. Rodney G Downey and Michael Ralph Fellows. Parameterized complexity. Springer Science and Business Media, 2012. Google Scholar
  14. Pål Grønås Drange, Markus Sortland Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Fernando Sánchez Villaamil, Saket Saurabh, Sebastian Siebertz, and Somnath Sikdar. Kernelization and sparseness: the case of dominating set. In Nicolas Ollinger and Heribert Vollmer, editors, 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, volume 47 of LIPIcs, pages 31:1-31:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. Google Scholar
  15. Eduard Eiben, Mithilesh Kumar, Amer E. Mouawad, Fahad Panolan, and Sebastian Siebertz. Lossy kernels for connected dominating set on sparse graphs. SIAM J. Discret. Math., 33(3):1743-1771, 2019. Google Scholar
  16. Guy Even, Dror Rawitz, and Shimon Shahar. Hitting sets when the vc-dimension is small. Inf. Process. Lett., 95(2):358-362, 2005. Google Scholar
  17. Grzegorz Fabianski, Michal Pilipczuk, Sebastian Siebertz, and Szymon Torunczyk. Progressive algorithms for domination and independence. In Rolf Niedermeier and Christophe Paul, editors, 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany, volume 126 of LIPIcs, pages 27:1-27:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  18. Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, and Pasin Manurangsi. A survey on approximation in parameterized complexity: Hardness and algorithms. Algorithms, 13(6):146, 2020. Google Scholar
  19. Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms. Springer-Verlag, Berlin, Heidelberg, 1st edition, 2010. Google Scholar
  20. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Kernels for (connected) dominating set on graphs with excluded topological minors. ACM Trans. Algorithms, 14(1):6:1-6:31, 2018. Google Scholar
  21. Jacob Fox, Tim Roughgarden, C. Seshadhri, Fan Wei, and Nicole Wein. Finding cliques in social networks: A new distribution-free model. SIAM J. Comput., 49(2):448-464, 2020. Google Scholar
  22. Edin Husic and Tim Roughgarden. FPT algorithms for finding dense subgraphs in c-closed graphs. CoRR, abs/2007.09768, 2020. URL: http://arxiv.org/abs/2007.09768.
  23. Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Computing dense and sparse subgraphs of weakly closed graphs. In Yixin Cao, Siu-Wing Cheng, and Minming Li, editors, 31st International Symposium on Algorithms and Computation, ISAAC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference), volume 181 of LIPIcs, pages 20:1-20:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  24. Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Exploiting c-closure in kernelization algorithms for graph problems. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 65:1-65:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  25. Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Essentially tight kernels for (weakly) closed graphs. CoRR, abs/2103.03914, 2021. URL: http://arxiv.org/abs/2103.03914.
  26. V. S. Anil Kumar, Sunil Arya, and H. Ramesh. Hardness of set cover with intersection 1. In Ugo Montanari, José D. P. Rolim, and Emo Welzl, editors, Automata, Languages and Programming, 27th International Colloquium, ICALP 2000, Geneva, Switzerland, July 9-15, 2000, Proceedings, volume 1853 of Lecture Notes in Computer Science, pages 624-635. Springer, 2000. Google Scholar
  27. Geevarghese Philip, Venkatesh Raman, and Somnath Sikdar. Solving dominating set in larger classes of graphs: FPT algorithms and polynomial kernels. In Amos Fiat and Peter Sanders, editors, Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings, volume 5757 of Lecture Notes in Computer Science, pages 694-705. Springer, 2009. Google Scholar
  28. Norbert Sauer. On the density of families of sets. J. Comb. Theory, Ser. A, 13(1):145-147, 1972. Google Scholar
  29. Saharon Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific Journal of Mathematics, 41(1):247-261, 1972. Google Scholar
  30. Sebastian Siebertz. Greedy domination on biclique-free graphs. Inf. Process. Lett., 145:64-67, 2019. Google Scholar
  31. Vijay V. Vazirani. Approximation Algorithms. Springer-Verlag, Berlin, Heidelberg, 2001. 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