Document Open Access Logo

Graph Searching Games and Width Measures for Directed Graphs

Authors Saeed Akhoondian Amiri, Lukasz Kaiser, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz

PDF
Thumbnail PDF

File

LIPIcs.STACS.2015.34.pdf
  • Filesize: 0.66 MB
  • 14 pages

Document Identifiers

Author Details

Saeed Akhoondian Amiri
Lukasz Kaiser
Stephan Kreutzer
Roman Rabinovich
Sebastian Siebertz

Cite As Get BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 34-47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.STACS.2015.34

Abstract

In cops and robber games a number of cops tries to capture a robber in  
a graph. A variant of these games on undirected graphs characterises tree width by the least number of cops needed to win. We consider cops and robber games on digraphs and width measures (such as DAG-width, directed tree width or D-width) corresponding to them. All of them generalise tree width and the game characterising it. 

For the DAG-width game we prove that the problem to decide the minimal
number of cops required to capture the robber (which is the same as deciding DAG-width), is PSPACE-complete, in contrast to most other similar games. We also show that the cop-monotonicity cost for directed tree width games cannot be bounded by any function. As a consequence, D-width is not bounded in directed tree width, refuting a conjecture by Safari.

A large number of directed width measures generalising tree width has been proposed in the literature. However, only very little was known about the relation between them, in particular about whether classes of digraphs of bounded width in one measure have bounded width in another. In this paper we establish an almost complete order among the most prominent width measures with respect to mutual boundedness.

Subject Classification

Keywords
  • cops and robber games
  • directed graphs
  • DAG-width

Metrics

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

References

  1. I. Adler. Directed tree-width examples. J. Comb. Theory, Ser. B, 97(5):718-725, 2007. Google Scholar
  2. J. Barát. Directed Path-width and Monotonicity in Digraph Searching. Graphs and Comb., 22(2), 2006. Google Scholar
  3. D. Berwanger, A. Dawar, P. Hunter, and S. Kreutzer. DAG-width and parity games. In STACS '06, volume 3884 of LNCS. Springer, 2006. Google Scholar
  4. D. Berwanger, A. Dawar, P. Hunter, S. Kreutzer, and J. Obdržálek. The DAG-width of directed graphs. J. Comb. Theory, 102(4):900-923, 2012. Google Scholar
  5. D. Bienstock and P. Seymour. Monotonicity in graph searching. Journal of Algorithms, 12(2):239-245, 1991. Google Scholar
  6. N. Dendris, L. Kirousis, and D. Thilikos. Fugitive search games on graphs and related parameters. Theoretical Computer Science, 172(1-2):233 - 254, 1997. Google Scholar
  7. D. Dereniowski. From pathwidth to connected pathwidth. In 28th Symposium on Theoretical Aspects of Computer Science (STACS), 2011. Google Scholar
  8. R. Diestel. Graph Theory, 4th Edition. Springer, 2012. Google Scholar
  9. F. Fomin, P. Golovach, and D. Thilikos. Approximation algorithms for domination search. In Klaus Jansen and Roberto Solis-Oba, editors, Approximation and Online Algorithms (WAOA), volume 6534 of Lecture Notes in Computer Science, pages 130-141. Springer Berlin / Heidelberg, 2011. Google Scholar
  10. F. Fomin, D. Kratsch, and H. Müller. On the domination search number. Discrete Applied Mathematics, 127(3):565-580, 2003. Google Scholar
  11. F. Fomin and D. Thilikos. On the monotonicity of games generated by symmetric submodular functions. Discrete Applied Mathematics, 131(2):323 - 335, 2003. Google Scholar
  12. F. Fomin and D. Thilikos. An annotated bibliography on guaranteed graph searching. Theoretical Computer Science, 399(3):236-245, 2008. Google Scholar
  13. P. Hunter and S. Kreutzer. Digraph measures: Kelly decompositions, games, and orderings. Theor. Comput. Sci., 399(3), 2008. Google Scholar
  14. T. Johnson, N. Robertson, P. Seymour, and R. Thomas. Directed Tree-Width. J. Comb. Theory, Ser. B, 82(1), 2001. Google Scholar
  15. S. Kreutzer. Graph searching games. In Krzysztof R. Apt and Erich Grädel, editors, Lectures in Game Theory for Computer Scientists, chapter 7, pages 213-263. CUP, 2011. Google Scholar
  16. S. Kreutzer and S. Ordyniak. Distance-d-domination games. In 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), 2009. Google Scholar
  17. S. Kreutzer and S. Ordyniak. Digraph decompositions and monotonicity in digraph searching. Theor. Comput. Sci., 412(35):4688-4703, 2011. Google Scholar
  18. A. S. LaPaugh. Recontamination does not help to search a graph. Journal of the ACM, 40:224-245, 1993. Google Scholar
  19. F. Mazoit and N. Nisse. Monotonicity of non-deterministic graph searching. Theor. Comput. Sci., 399(3):169-178, 2008. Google Scholar
  20. J. Obdržálek. Algorithmic analysis of parity games. PhD thesis, School of Informatics, University of Edinburgh, 2006. Google Scholar
  21. R. Rabinovich. Graph Complexity Measures and Monotonicity. PhD thesis, RWTH Aachen University, 2013. Google Scholar
  22. B. Reed. Introducing directed tree-width. Electronic Notes in Discrete Mathematics, 3:222 - 229, 1999. Google Scholar
  23. M. A. Safari. D-width: A more natural measure for directed tree width. In Joanna Jedrzejowicz and Andrzej Szepietowski, editors, MFCS, volume 3618 of Lecture Notes in Computer Science, pages 745-756. Springer, 2005. Google Scholar
  24. P. Seymour and R. Thomas. Graph searching and a min-max theorem for tree-width. J. Comb. Theory Ser. B, 58(1), 1993. Google Scholar
  25. Y. Stamatiou and D. Thilikos. Monotonicity and inert fugitive search games. In 6th Twente Workshop on Graphs and Combinatorial Optimization CTW 1999. University of Twente, Enschede, 1999. Google Scholar
  26. B. Yang and Y. Cao. Monotonicity of strong searching on digraphs. J. Comb. Optim., 14(4):411-425, 2007. Google Scholar
  27. B. Yang and Y. Cao. On the monotonicity of weak searching. In COCOON, pages 52-61, 2008. 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