Document Open Access Logo

Lossy Kernels for Connected Dominating Set on Sparse Graphs

Authors Eduard Eiben, Mithilesh Kumar, Amer E. Mouawad, Fahad Panolan, Sebastian Siebertz

PDF
Thumbnail PDF

File

LIPIcs.STACS.2018.29.pdf
  • Filesize: 0.54 MB
  • 15 pages

Document Identifiers

Author Details

Eduard Eiben
Mithilesh Kumar
Amer E. Mouawad
Fahad Panolan
Sebastian Siebertz

Cite As Get BibTex

Eduard Eiben, Mithilesh Kumar, Amer E. Mouawad, Fahad Panolan, and Sebastian Siebertz. Lossy Kernels for Connected Dominating Set on Sparse Graphs. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.STACS.2018.29

Abstract

For alpha > 1, an alpha-approximate (bi-)kernel for a problem Q is a polynomial-time algorithm that takes as input an instance (I, k) of Q and outputs an instance (I',k') (of a problem Q') of size bounded by a function of k such that, for every c >= 1, a c-approximate solution for the new instance can be turned into a (c alpha)-approximate solution of the original instance in polynomial time. This framework of lossy kernelization was recently introduced by Lokshtanov et al. We study Connected Dominating Set (and its distance-r variant) parameterized by solution size on sparse graph classes like biclique-free graphs, classes of bounded expansion, and nowhere dense classes. We prove that for every alpha > 1, Connected Dominating Set admits a polynomial-size alpha-approximate (bi-)kernel on all the aforementioned classes. Our results are in sharp contrast to the kernelization complexity of Connected Dominating Set, which is known to not admit a polynomial kernel even on 2-degenerate graphs and graphs of bounded expansion, unless NP \subseteq coNP/poly. We complement our results by the following conditional lower bound. We show that if a class C is somewhere dense and closed under taking subgraphs, then for some value of r \in N there cannot exist an alpha-approximate bi-kernel for the (Connected) Distance-r Dominating Set problem on C for any alpha > 1 (assuming the Gap Exponential Time Hypothesis).

Subject Classification

Keywords
  • Lossy Kernelization
  • Connected Dominating Set
  • Sparse Graph Classes

Metrics

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

References

  1. Jochen Alber, Michael R. Fellows, and Rolf Niedermeier. Polynomial-time data reduction for dominating set. J. ACM, 51(3):363-384, 2004. Google Scholar
  2. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier meets möbius: Fast subset convolution. In Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing, pages 67-74, New York, NY, USA, 2007. Google Scholar
  3. Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos. (Meta) Kernelization. In 50th Annual IEEE Symposium on Foundations of Computer Science, Atlanta, Georgia, USA, pages 629-638, 2009. Google Scholar
  4. Andreas Brandstädt, Van Bang Le, and Jeremy P. Spinrad. Graph Classes: A Survey. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1999. Google Scholar
  5. 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. arXiv preprint arXiv:1708.04218, 2017. Google Scholar
  6. Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms, volume 3. Springer, 2015. Google Scholar
  7. Marek Cygan, Fabrizio Grandoni, and Danny Hermelin. Tight kernel bounds for problems on graphs with small degeneracy - (extended abstract). In Algorithms - ESA 2013 - 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings, pages 361-372, 2013. Google Scholar
  8. Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk. Kernelization hardness of connectivity problems in d-degenerate graphs. Discrete Applied Mathematics, 160(15):2131-2141, 2012. Google Scholar
  9. Anuj Dawar and Stephan Kreutzer. Domination problems in nowhere-dense classes. In FSTTCS 2009, volume 4 of LIPIcs, pages 157-168. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2009. Google Scholar
  10. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  11. Rodney G Downey and Michael R Fellows. Fundamentals of parameterized complexity, volume 4. Springer, 2013. Google Scholar
  12. Rodney G Downey and Michael Ralph Fellows. Parameterized complexity. Springer, 1999. Google Scholar
  13. 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 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, pages 31:1-31:14, 2016. Google Scholar
  14. Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer, O-joung Kwon, Michal Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. Neighborhood complexity and kernelization for nowhere dense classes of graphs. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, pages 63:1-63:14, 2017. Google Scholar
  15. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Bidimensionality and kernels. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, Austin, Texas, USA, pages 503-510, 2010. Google Scholar
  16. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Linear kernels for (connected) dominating set on H-minor-free graphs. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 82-93, 2012. Google Scholar
  17. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs. In 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, February 27 - March 2, 2013, Kiel, Germany, pages 92-103, 2013. Google Scholar
  18. Jakub Gajarský, Petr Hlinený, Jan Obdrzálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar. Kernelization using structural parameters on sparse graph classes. J. Comput. Syst. Sci., 84:219-242, 2017. URL: http://dx.doi.org/10.1016/j.jcss.2016.09.002.
  19. Sariel Har-Peled and Kent Quanrud. Approximation algorithms for polynomial-expansion and low-density graphs, 2015. (CoRR/abs/1501.00721). URL: http://arxiv.org/abs/1501.00721.
  20. Sariel Har-Peled and Kent Quanrud. Approximation algorithms for polynomial-expansion and low-density graphs. In Nikhil Bansal and Irene Finocchi, editors, Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, volume 9294 of Lecture Notes in Computer Science, pages 717-728. Springer, 2015. Google Scholar
  21. Stephan Kreutzer, Roman Rabinovich, and Sebastian Siebertz. Polynomial kernels and wideness properties of nowhere dense graph classes. In SODA, pages 1533-1545. SIAM, 2017. Google Scholar
  22. Daniel Lokshtanov, Matthias Mnich, and Saket Saurabh. A linear kernel for a planar connected dominating set. Theor. Comput. Sci., 412(23):2536-2543, 2011. Google Scholar
  23. Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. Lossy kernelization. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 224-237, 2017. Google Scholar
  24. Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, Saket Saurabh, and Somnath Sikdar. FPT algorithms for connected feedback vertex set. In WALCOM: Algorithms and Computation, 4th International Workshop, WALCOM 2010, Dhaka, Bangladesh, February 10-12, 2010. Proceedings, pages 269-280, 2010. Google Scholar
  25. Jaroslav Nešetřil and Patrice Ossona de Mendez. Grad and classes with bounded expansion I. Decompositions. European Journal of Combinatorics, 29(3):760-776, 2008. Google Scholar
  26. Jaroslav Nešetřil and Patrice Ossona de Mendez. Grad and classes with bounded expansion II. Algorithmic aspects. European Journal of Combinatorics, 29(3):777-791, 2008. Google Scholar
  27. Jaroslav Nešetřil and Patrice Ossona de Mendez. Grad and classes with bounded expansion III. Restricted graph homomorphism dualities. European Journal of Combinatorics, 29(4):1012-1024, 2008. Google Scholar
  28. Jaroslav Nešetřil and Patrice Ossona de Mendez. First order properties on nowhere dense structures. The Journal of Symbolic Logic, 75(03):868-887, 2010. Google Scholar
  29. Jaroslav Nešetřil and Patrice Ossona de Mendez. On nowhere dense graphs. European Journal of Combinatorics, 32(4):600-617, 2011. Google Scholar
  30. Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. Google Scholar
  31. Geevarghese Philip, Venkatesh Raman, and Somnath Sikdar. Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond. ACM Trans. Algorithms, 9(1):11, 2012. Google Scholar
  32. Michał Pilipczuk, Sebastian Siebertz, and Szymon Toruńczyk. On wideness and stability. arXiv preprint arXiv:1705.09336, 2017. Google Scholar
  33. Norbert Sauer. On the density of families of sets. Journal of Combinatorial Theory, Series A, 13(1):145-147, 1972. Google Scholar
  34. 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
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 About DROPS Imprint Privacy Contact