Document Open Access Logo

Kernelization and Sparseness: the Case of Dominating Set

Authors Pål Grønås Drange, Markus Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Fernando Sánchez Villaamil, Saket Saurabh, Sebastian Siebertz, Somnath Sikdar

PDF
Thumbnail PDF

File

LIPIcs.STACS.2016.31.pdf
  • Filesize: 0.71 MB
  • 14 pages

Document Identifiers

Author Details

Pål Grønås Drange
Markus Dregi
Fedor V. Fomin
Stephan Kreutzer
Daniel Lokshtanov
Marcin Pilipczuk
Michal Pilipczuk
Felix Reidl
Fernando Sánchez Villaamil
Saket Saurabh
Sebastian Siebertz
Somnath Sikdar

Cite AsGet BibTex

Pål Grønås Drange, Markus 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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.STACS.2016.31

Abstract

We prove that for every positive integer r and for every graph class G of bounded expansion, the r-DOMINATING SET problem admits a linear kernel on graphs from G. Moreover, in the more general case when G is only assumed to be nowhere dense, we give an almost linear kernel on G for the classic DOMINATING SET problem, i.e., for the case r=1. These results generalize a line of previous research on finding linear kernels for DOMINATING SET and r-DOMINATING SET (Alber et al., JACM 2004, Bodlaender et al., FOCS 2009, Fomin et al., SODA 2010, Fomin et al., SODA 2012, Fomin et al., STACS 2013). However, the approach taken in this work, which is based on the theory of sparse graphs, is radically different and conceptually much simpler than the previous approaches. We complement our findings by showing that for the closely related CONNECTED DOMINATING SET problem, the existence of such kernelization algorithms is unlikely, even though the problem is known to admit a linear kernel on H-topological-minor-free graphs (Fomin et al., STACS 2013). Also, we prove that for any somewhere dense class G, there is some r for which r-DOMINATING SET is W[2]-hard on G. Thus, our results fall short of proving a sharp dichotomy for the parameterized complexity of r-DOMINATING SET on subgraph-monotone graph classes: we conjecture that the border of tractability lies exactly between nowhere dense and somewhere dense graph classes.
Keywords
  • kernelization
  • dominating set
  • bounded expansion
  • nowhere dense

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. Noga Alon and Shai Gutner. Kernels for the Dominating Set problem on graphs with an excluded minor. Electronic Colloquium on Comp. Complexity (ECCC), 15(066), 2008. Google Scholar
  3. H. Bodlaender, F. V. Fomin, D. Lokshtanov, E. Penninkx, S. Saurabh, and D. M. Thilikos. (Meta) Kernelization. In Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS), pages 629-638. IEEE, 2009. Google Scholar
  4. 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, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 629-638. IEEE Computer Society, 2009. Google Scholar
  5. Marek Cygan, Fabrizio Grandoni, and Danny Hermelin. Tight kernel bounds for problems on graphs with small degeneracy. In Proc. of the 21st Annual European Symp. on Algorithms (ESA), volume 8125 of LNCS, pages 361-372. Springer, 2013. Google Scholar
  6. Anuj Dawar, Martin Grohe, and Stephan Kreutzer. Locally excluding a minor. In Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS), pages 270-279. IEEE Computer Society, 2007. Google Scholar
  7. Anuj Dawar and Stephan Kreutzer. Domination problems in nowhere-dense classes. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 4 of Leibniz International Proceedings in Informatics (LIPIcs), pages 157-168. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2009. Google Scholar
  8. Rodney G. Downey and Michael R. Fellows. Parameterized complexity. Springer-Verlag, New York, 1999. Google Scholar
  9. Pål Grønås Drange, Markus Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Felix Reidl, Saket Saurabh, Fernando Sánchez Villaamil, and Somnath Sikdar. Kernelization and Sparseness: the case of Dominating Set. CoRR, abs/1309.4022v1, 2014. Google Scholar
  10. Z. Dvořák. Constant-factor approximation of the domination number in sparse graphs. Eur. J. Comb., 34(5):833-840, 2013. Google Scholar
  11. Zdenek Dvořák, Daniel Král', and Robin Thomas. Testing first-order properties for subclasses of sparse graphs. J. ACM, 60(5):36, 2013. Google Scholar
  12. Jörg Flum and Martin Grohe. Fixed-parameter tractability, definability, and model-checking. SIAM J. Comput., 31(1):113-145, 2001. Google Scholar
  13. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag, Berlin, 2006. Google Scholar
  14. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Bidimensionality and kernels. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 503-510. SIAM, 2010. Google Scholar
  15. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Linear kernels for (Connected) Dominating Set on H-minor-free graphs. In Proc. of the 22nd Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 82-93. SIAM, 2012. Google Scholar
  16. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Linear kernels for (Connected) Dominating Set on graphs with excluded topological subgraphs. In Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 20 of Leibniz International Proceedings in Informatics (LIPIcs), pages 92-103. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2013. Google Scholar
  17. Markus Frick and Martin Grohe. Deciding first-order properties of locally tree-decomposable structures. J. ACM, 48(6):1184-1206, 2001. Google Scholar
  18. J. Gajarský, P. Hliněný, J. Obdržálek, S. Ordyniak, F. Reidl, P. Rossmanith, F. Sánchez Villaamil, and S. Sikdar. Kernelization using structural parameters on sparse graph classes. In Proceedings of the 21st Annual European Symposium on Algorithms (ESA), volume 8125 of Lecture Notes in Comput. Sci., pages 529-540. Springer, 2013. Full version available at URL: http://arxiv.org/abs/1302.6863.
  19. Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), pages 89-98. ACM, 2014. Google Scholar
  20. Martin Grohe and Dániel Marx. Structure theorem and isomorphism test for graphs with excluded topological subgraphs. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), pages 173-192. ACM, 2012. Google Scholar
  21. Shai Gutner. Polynomial kernels and faster algorithms for the Dominating Set problem on graphs with an excluded minor. In Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC), volume 5917 of Lecture Notes in Comput. Sci., pages 246-257. Springer, 2009. Google Scholar
  22. Stephan Kreutzer. Algorithmic meta-theorems. In J. Esparza, C. Michaux, and C. Steinhorn, editors, Finite and Algorithmic Model Theory, chapter 5, pages 177-270. Cambridge University Press, 2011. Google Scholar
  23. J. Nešetřil and P. Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms, volume 28 of Algorithms and Combinatorics. Springer, 2012. Google Scholar
  24. Geevarghese Philip, Venkatesh Raman, and Somnath Sikdar. Polynomial kernels for Dominating Set in graphs of bounded degeneracy and beyond. ACM Transactions on Algorithms, 9(1):11, 2012. URL: http://dx.doi.org/10.1145/2390176.2390187.
  25. Felix Reidl. Structural sparseness and complex networks. Dr., Aachen, Techn. Hochsch., Aachen, 2015. Aachen, Techn. Hochsch., Diss., 2015. URL: https://publications.rwth-aachen.de/record/565064.
  26. Neil Robertson and Paul D. Seymour. Graph Minors. XVI. Excluding a non-planar graph. J. Comb. Theory, Ser. B, 89(1):43-76, 2003. Google Scholar
  27. Detlef Seese. Linear time computable problems and first-order descriptions. Mathematical Structures in Computer Science, 6(6):505-526, 1996. 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