Document Open Access Logo

Structural Properties and Constant Factor-Approximation of Strong Distance-r Dominating Sets in Sparse Directed Graphs

Authors Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, Grischa Weberstädt

PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.48.pdf
  • Filesize: 0.49 MB
  • 15 pages

Document Identifiers

Author Details

Stephan Kreutzer
Roman Rabinovich
Sebastian Siebertz
Grischa Weberstädt

Cite As Get BibTex

Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, and Grischa Weberstädt. Structural Properties and Constant Factor-Approximation of Strong Distance-r Dominating Sets in Sparse Directed Graphs. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 48:1-48:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.STACS.2017.48

Abstract

Bounded expansion and nowhere dense graph classes, introduced by Nesetril and Ossona de Mendez, form a large variety of classes of uniformly sparse graphs which includes the class of planar graphs, actually all classes with excluded minors, and also bounded degree graphs. Since their initial definition it was shown that these graph classes can be defined in many equivalent ways: by generalised colouring numbers, neighbourhood complexity, sparse neighbourhood covers, a game known as the splitter game, and many more. 

We study the corresponding concepts for directed graphs. We show that the densities of bounded depth directed minors and bounded depth topological minors relate in a similar way as in the undirected case. We provide a characterisation of bounded expansion classes by a directed version of the generalised colouring numbers. As an application we show how to construct sparse directed neighbourhood covers and how to approximate directed distance-r dominating sets on classes of bounded expansion. On the other hand, we show that linear neighbourhood complexity does not characterise directed classes of bounded expansion.

Subject Classification

Keywords
  • Directed Graph Structure Theory
  • Bounded Expansion
  • Generalised Colouring Numbers
  • Splitter Game
  • Approximation Algorithms
  • Dominating Set

Metrics

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

References

  1. Saeed Akhoondian Amiri, Lukasz Kaiser, Stephan Kreutzer, Roman Rabinovich, and Sebastian Siebertz. Graph searching games and width measures for directed graphs. In 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, pages 34-47, 2015. Google Scholar
  2. Jørgen Bang-Jensen and Gregory Z. Gutin. Digraphs: theory, algorithms and applications. Springer Science &Business Media, 2008. Google Scholar
  3. Dietmar Berwanger, Anuj Dawar, Paul Hunter, and Stephan Kreutzer. Dag-width and parity games. In Symp. on Theoretical Aspects of Computer Science (STACS), 2006. Google Scholar
  4. Dietmar Berwanger, Anuj Dawar, Paul Hunter, Stephan Kreutzer, and Jan Obdrzálek. The dag-width of directed graphs. J. Comb. Theory, Ser. B, 102(4):900-923, 2012. URL: http://dx.doi.org/10.1016/j.jctb.2012.04.004.
  5. Dietmar Berwanger, Erich Grädel, Lukasz Kaiser, and Roman Rabinovich. Entanglement and the complexity of directed graphs. Theor. Comput. Sci., 463:2-25, 2012. URL: http://dx.doi.org/10.1016/j.tcs.2012.07.010.
  6. Guantao Chen and Richard H. Schelp. Graphs with linearly bounded ramsey numbers. J. Combin. Theory Ser. B, 57:138-149, 1993. Google Scholar
  7. Marek Cygan, Fedor V. Fomin, Ł ukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  8. Anuj Dawar and Stephan Kreutzer. Domination problems in nowhere-dense classes of graphs. In Foundations of software technology and theoretical computer science (FSTTCS), pages 157-168, 2009. Google Scholar
  9. Pål Grønås Drange, Markus S. Dregi, Fedor V Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Felix Reidl, Saket Saurabh, Fernando Sánchez Villaamil, Sebastian Siebertz, et al. Kernelization and sparseness: the case of dominating set. arXiv preprint arXiv:1411.4575, 2014. Google Scholar
  10. Zdenek Dvorák. Asymptotical structure of combinatorial objects. Charles University, Faculty of Mathematics and Physics, 51:357-422, 2007. Google Scholar
  11. Zdeněk Dvořák. Constant-factor approximation of the domination number in sparse graphs. European Journal of Combinatorics, 34(5):833-840, 2013. Google Scholar
  12. Zdenek Dvorak, Daniel Král, and Robin Thomas. Testing first-order properties for subclasses of sparse graphs. J. ACM, 60(5):36, 2013. Google Scholar
  13. Jakub Gajarskỳ, Petr Hliněnỳ, Jan Obdržálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sanchez Villaamil, and Somnath Sikdar. Kernelization using structural parameters on sparse graph classes. In European Symposium on Algorithms, pages 529-540. Springer, 2013. Google Scholar
  14. Robert Ganian, Petr Hliněný, Joachim Kneis, Daniel Meister, Jan Obdržálek, Peter Rossmanith, and Somnath Sikdar. Are there any good digraph width measures? In Venkatesh Raman and Saket Saurabh, editors, Parameterized and Exact Computation, volume 6478 of Lecture Notes in Computer Science, pages 135-146. Springer Berlin Heidelberg, 2010. URL: http://dx.doi.org/10.1007/978-3-642-17493-3_14.
  15. Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, and Konstantinos Stavropoulos. Colouring and covering nowhere dense graphs. In Graph-Theoretic Concepts in Computer Science - 41st International Workshop, WG 2015, Garching, Germany, June 17-19, 2015, Revised Papers, pages 325-338, 2015. Google Scholar
  16. 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, pages 89-98. ACM, 2014. Google Scholar
  17. Thor Johnson, Neil Robertson, Paul D. Seymour, and Robin Thomas. Directed tree-width. Journal of Combinatorial Theory, Series B, 82(1):138-154, 2001. Google Scholar
  18. Hal A. Kierstead. A simple competitive graph coloring algorithm. J. Combin. Theory Ser. B, 78:57-68, 2000. Google Scholar
  19. Hal A. Kierstead and William T. Trotter. Planar graph coloring with an uncooperative partner. In W.T. Trotter, editor, Planar Graphs, volume 9 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 85-93. AMS, 1993. Google Scholar
  20. Hal A. Kierstead and Daqing Yang. Orderings on graphs and game coloring number. Order, 20:255-264, 2003. Google Scholar
  21. Stephan Kreutzer and Sebastian Ordyniak. Digraph decompositions and monotonicity in digraph searching. In Graph-Theoretic Concepts in Computer Science, 34th International Workshop, WG 2008, Durham, UK, June 30 - July 2, 2008. Revised Papers, pages 336-347, 2008. Google Scholar
  22. Stephan Kreutzer, Michał Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. The generalised colouring numbers on classes of bounded expansion. In 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, 2016 - Kraków, Poland, pages 85:1-85:13, 2016. Google Scholar
  23. Stephan Kreutzer and Siamak Tazari. Directed nowhere dense classes of graphs. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 1552-1562. SIAM, 2012. Google Scholar
  24. Michael Lampis, Georgia Kaouri, and Valia Mitsou. On the algorithmic effectiveness of digraph decompositions and complexity measures. Discrete Optimization, 8(1):129-138, 2011. Google Scholar
  25. Daniel Meister, Jan Arne Telle, and Martin Vatshelle. Characterization and recognition of digraphs of bounded kelly-width. In Workshop on Graph Theoretical Aspects of Computer Science (WG), pages 270-279, 2007. URL: http://dx.doi.org/10.1007/978-3-540-74839-7_26.
  26. 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
  27. Jaroslav Nešetřil and Patrice Ossona de Mendez. On nowhere dense graphs. European Journal of Combinatorics, 32(4):600-617, 2011. Google Scholar
  28. Jaroslav Nešetřil and Patrice Ossona De Mendez. On low tree-depth decompositions. Graphs and Combinatorics, 31(6):1941-1963, 2015. Google Scholar
  29. Jaroslav Nešetřil and Patrice Ossona de Mendez. Grad and classes with bounded expansion I-III. European Journal of Combinatorics, 29, 2008. Series of 3 papers appearing in volumes (3) and (4). Google Scholar
  30. Jan Obdrzálek. Dag-width: connectivity measure for directed graphs. In Symp. on Discrete Algorithms (SODA), pages 814-821, 2006. Google Scholar
  31. Ran Raz and Shmuel Safra. A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In Proceedings of the twenty-ninth annual ACM Symposium on Theory of Computing, page 475–484, 1997. Google Scholar
  32. Felix Reidl. Structural sparseness and complex networks. Dr., Aachen, Techn. Hochsch., Aachen, 2016. Google Scholar
  33. Felix Reidl, Fernando Sánchez Villaamil, and Konstantinos Stavropoulos. Characterising bounded expansion by neighbourhood complexity. arXiv preprint arXiv:1603.09532, 2016. Google Scholar
  34. Mohammad Ali Safari. D-width: A more natural measure for directed tree width. In Proc. of Mathematical Foundations of Computer Science (MFCS), number 3618 in Lecture Notes in Computer Science, pages 745-756, 2005. Google Scholar
  35. Norbert Sauer. On the density of families of sets. Journal of Combinatorial Theory, Series A, 13(1):145-147, 1972. Google Scholar
  36. 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
  37. Vladimir N. Vapnik and Alexey Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In Measures of Complexity, pages 11-30. Springer, 2015. Google Scholar
  38. Xuding Zhu. Colouring graphs with bounded generalized colouring number. Discrete Mathematics, 309(18):5562-5568, 2009. 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