Document Open Access Logo

Progressive Algorithms for Domination and Independence

Authors Grzegorz Fabiański, Michał Pilipczuk, Sebastian Siebertz, Szymon Toruńczyk

PDF
Thumbnail PDF

File

LIPIcs.STACS.2019.27.pdf
  • Filesize: 0.84 MB
  • 16 pages

Document Identifiers

Author Details

Grzegorz Fabiański
  • Faculty of Mathematics, Informatics, and Mechanics, University of Warsaw, Poland
Michał Pilipczuk
  • Institute of Informatics, University of Warsaw, Poland
Sebastian Siebertz
  • Institute of Informatics, Humboldt-Universität zu Berlin, Germany
Szymon Toruńczyk
  • Institute of Informatics, University of Warsaw, Poland

Funding

The work of M. Pilipczuk and S. Siebertz is supported by the National Science Centre of Poland via POLONEZ grant agreement UMO-2015/19/P/ST6/03998, which has received funding from the European Union’s Horizon 2020 research and innovation programme (Marie Skłodowska-Curie grant agreement No. 665778). G. Fabia{ń}ski and Sz. Toru{ń}czyk are supported by the NCN grant 2016/21/D/ST6/01485.

Acknowledgements

We thank Ehud Hrushovski for pointing us to the nfcp property.

Cite AsGet BibTex

Grzegorz Fabiański, Michał Pilipczuk, Sebastian Siebertz, and Szymon Toruńczyk. Progressive Algorithms for Domination and Independence. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.STACS.2019.27

Abstract

We consider a generic algorithmic paradigm that we call progressive exploration, which can be used to develop simple and efficient parameterized graph algorithms. We identify two model-theoretic properties that lead to efficient progressive algorithms, namely variants of the Helly property and stability. We demonstrate our approach by giving linear-time fixed-parameter algorithms for the Distance-r Dominating Set problem (parameterized by the solution size) in a wide variety of restricted graph classes, such as powers of nowhere dense classes, map graphs, and (for r=1) biclique-free graphs. Similarly, for the Distance-r Independent Set problem the technique can be used to give a linear-time fixed-parameter algorithm on any nowhere dense class. Despite the simplicity of the method, in several cases our results extend known boundaries of tractability for the considered problems and improve the best known running times.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Fixed parameter tractability
  • Theory of computation → Finite Model Theory
Keywords
  • Dominating Set
  • Independent Set
  • nowhere denseness
  • stability
  • fixed-parameter tractability

Metrics

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

Related Versions

References

  1. Hans Adler and Isolde Adler. Interpreting nowhere dense graph classes as a classical notion of model theory. European Journal of Combinatorics, 36:322-330, 2014. Google Scholar
  2. Zhi-Zhong Chen. Approximation Algorithms for Independent Sets in Map Graphs. J. Algorithms, 41(1):20-40, 2001. Google Scholar
  3. Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and computation, 85(1):12-75, 1990. Google Scholar
  4. 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
  5. Anuj Dawar and Stephan Kreutzer. Parameterized complexity of first-order logic. In Electronic Colloquium on Computational Complexity, TR09-131, page 39, 2009. Google Scholar
  6. Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos. Fixed-parameter algorithms for (k,r)-center in planar graphs and map graphs. ACM Trans. Algorithms, 1(1):33-47, 2005. Google Scholar
  7. Pål Grønås Drange, Markus Sortland Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Felix Reidl, Fernando Sánchez Villaamil, Saket Saurabh, Sebastian Siebertz, and Somnath Sikdar. Kernelization and Sparseness: the Case of Dominating Set. In STACS 2016, volume 47 of LIPIcs, pages 31:1-31:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. Full version available as arxiv preprint https://arxiv.org/abs/1411.4575. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2016.31.
  8. Zdeněk 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
  9. Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer, O-joung Kwon, Michał Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. Neighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs. In ICALP 2017, volume 80 of LIPIcs, pages 63:1-63:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Full version available as arxiv preprint https://arxiv.org/abs/1612.08197. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.63.
  10. Grzegorz Fabiański, Michał Pilipczuk, Sebastian Siebertz, and Szymon Toruńczyk. Progressive Algorithms for Domination and Independence. arXiv preprint, 2018. URL: http://arxiv.org/abs/1811.06799.
  11. Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding First-Order Properties of Nowhere Dense Graphs. J. ACM, 64(3):17:1-17:32, 2017. Google Scholar
  12. 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
  13. Jaroslav Nešetřil and Patrice Ossona de Mendez. On nowhere dense graphs. European Journal of Combinatorics, 32(4):600-617, 2011. Google Scholar
  14. Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. Google Scholar
  15. Allen O’Hara. An Introduction to Equations and Equational Theories, 2011. Google Scholar
  16. Michał Pilipczuk and Sebastian Siebertz. Kernelization and approximation of distance-r independent sets on nowhere dense graphs. arXiv preprint, 2018. URL: https://arxiv.org/abs/1809.05675.
  17. Michał Pilipczuk and Sebastian Siebertz. Lecture notes for the course "Sparsity" given at Faculty of Mathematics, Informatics, and Mechanics of the University of Warsaw, Winter Semester 2017/18. Available at URL: https://www.mimuw.edu.pl/~mp248287/sparsity.
  18. Michał Pilipczuk, Sebastian Siebertz, and Szymon Toruńczyk. On the number of types in sparse graphs. In LICS 2018, pages 799-808. ACM, 2018. Google Scholar
  19. Anand Pillay and Gabriel Srour. Closed Sets and Chain Conditions in Stable Theories. J. Symb. Log., 49:1350-1362, 1984. Google Scholar
  20. Klaus-Peter Podewski and Martin Ziegler. Stable graphs. Fundamenta Mathematicae, 100(2):101-107, 1978. Google Scholar
  21. Saharon Shelah. Classification theory: and the number of non-isomorphic models, volume 92. Elsevier, 1990. Google Scholar
  22. Jan Arne Telle and Yngve Villanger. FPT algorithms for domination in biclique-free graphs. In ESA 2012, volume 7501 of LNCS, pages 802-812. Springer, 2012. Google Scholar
  23. Mikkel Thorup. Map Graphs in Polynomial Time. In FOCS 1998, pages 396-405. IEEE Computer Society, 1998. 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