Document Open Access Logo

A Timecop’s Work Is Harder Than You Think

Authors Nils Morawietz, Carolin Rehs, Mathias Weller

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2020.71.pdf
  • Filesize: 0.55 MB
  • 14 pages

Document Identifiers

Author Details

Nils Morawietz
  • Fachbereich Mathematik und Informatik, Philipps-Universität Marburg, Germany
Carolin Rehs
  • Institute of Computer Science, Heinrich Heine Universität, Düsseldorf, Germany
Mathias Weller
  • CNRS, LIGM, Université Gustave Eiffel, Marne-la-Vallée, France

Acknowledgements

We thank our anonymous reviewers for their various helpful suggestions, in particular the connection to Tally-DFAs.

Cite As Get BibTex

Nils Morawietz, Carolin Rehs, and Mathias Weller. A Timecop’s Work Is Harder Than You Think. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 71:1-71:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.MFCS.2020.71

Abstract

We consider the (parameterized) complexity of a cop and robber game on periodic, temporal graphs and a problem on periodic sequences to which these games relate intimately. In particular, we show that it is NP-hard to decide (a) whether there is some common index at which all given periodic, binary sequences are 0, and (b) whether a single cop can catch a single robber on an edge-periodic temporal graph. We further present results for various parameterizations of both problems and show that hardness not only applies in general, but also for highly limited instances. As one main result we show that even if the graph has a size-2 vertex cover and is acyclic in each time step, the cop and robber game on periodic, temporal graphs is NP-hard and W[1]-hard when parameterized by the size of the underlying input graph.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Dynamic graph algorithms
Keywords
  • edge-periodic temporal graphs
  • cops and robbers
  • tally-intersection
  • congruence satisfyability

Metrics

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

References

  1. Eleni C. Akrida, George B. Mertzios, and Paul G. Spirakis. The temporal explorer who returns to the base. In Algorithms and Complexity, pages 13-24, Cham, 2019. Springer. Google Scholar
  2. Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis, and Viktor Zamaraev. Temporal vertex cover with a sliding time window. Journal of Computer and System Sciences, 107:108-123, 2020. Google Scholar
  3. Saeed Akhoondian Amiri, Lukasz Kaiser, Stephan Kreutzer, Roman Rabinovich, and Sebastian Siebertz. Graph Searching Games and Width Measures for Directed Graphs. In 32nd STACS'15, volume 30 of LIPIcs, pages 34-47, Dagstuhl, Germany, 2015. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. Google Scholar
  4. János Barát. Directed path-width and monotonicity in digraph searching. Graphs and Combinatorics, 22(2):161-172, 2006. Google Scholar
  5. Dietmar Berwanger, Anuj Dawar, Paul Hunter, and Stephan Kreutzer. Dag-width and parity games. In Annual Symposium on Theoretical Aspects of Computer Science, pages 524-536. Springer, 2006. Google Scholar
  6. Étienne Bézout. Théorie générale des équations algébriques par M. Bézout. de l'imprimerie de Ph.-D. Pierres, rue S. Jacques, 1779. Google Scholar
  7. Hans L Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theoretical computer science, 209(1-2):1-45, 1998. Google Scholar
  8. Graham R. Brightwell and Peter Winkler. Gibbs measures and dismantlable graphs. J. Comb. Theory Ser. B, 78(1):141–166, January 2000. Google Scholar
  9. Timothy H Chung, Geoffrey A Hollinger, and Volkan Isler. Search and pursuit-evasion in mobile robotics. Autonomous robots, 31(4):299, 2011. Google Scholar
  10. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  11. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  12. Thomas Erlebach, Michael Hoffmann, and Frank Kammer. On temporal graph exploration. In Automata, Languages, and Programming, pages 444-455. Springer, 2015. Google Scholar
  13. Thomas Erlebach and Jakob T Spooner. A game of cops and robbers on graphs with periodic edge-connectivity. In 46th SOFSEM'20, pages 64-75. Springer, 2020. Google Scholar
  14. Henning Fernau and Andreas Krebs. Problems on finite automata and the exponential time hypothesis. Algorithms, 10(1):24, 2017. Google Scholar
  15. Till Fluschnik, Hendrik Molter, Rolf Niedermeier, Malte Renken, and Philipp Zschoche. Temporal graph classes: A view through temporal separators. Theoretical Computer Science, 806:197-218, 2020. Google Scholar
  16. Fedor V Fomin and Dimitrios M Thilikos. An annotated bibliography on guaranteed graph searching. Theoretical computer science, 399(3):236-245, 2008. Google Scholar
  17. Frank Gurski, Carolin Rehs, and Jochen Rethmann. Knapsack problems: A parameterized point of view. Theoretical Computer Science, 775:93-108, 2019. Google Scholar
  18. Markus Holzer and Martin Kutrib. Descriptional and computational complexity of finite automata—a survey. Information and Computation, 209(3):456-470, 2011. Special Issue: 3rd International Conference on Language and Automata Theory and Applications (LATA 2009). Google Scholar
  19. Paul Hunter and Stephan Kreutzer. Digraph measures: Kelly decompositions‚ games‚ and orderings. Theoretical Computer Science (TCS), 399, 2008. Google Scholar
  20. Kenneth F. Ireland and Michael I. Rosen. A classical introduction to modern number theory, chapter Congruence, pages 28-38. Number 84 in Graduate texts in mathematics. Springer, New York, 2nd edition, 1990. Google Scholar
  21. 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
  22. David Kempe, Jon Kleinberg, and Amit Kumar. Connectivity and inference problems for temporal networks. Journal of Computer and System Sciences, 64(4):820-842, 2002. Google Scholar
  23. Nicolas Nisse. Network Decontamination. In Distributed Computing by Mobile Entities, volume 11340 of LNCS, pages 516-548. Springer, 2019. Google Scholar
  24. Richard Nowakowski and Ivan Rival. The smallest graph variety containing all paths. Discrete Mathematics, 43(2-3):223-234, 1983. Google Scholar
  25. Richard Nowakowski and Peter Winkler. Vertex-to-vertex pursuit in a graph. Discrete Math., 43(2–3):235–239, January 1983. Google Scholar
  26. Alain Quilliot. Jeux et pointes fixes sur les graphes. PhD thesis, Ph. D. Dissertation, Université de Paris VI, 1978. Google Scholar
  27. Paul D Seymour and Robin Thomas. Graph searching and a min-max theorem for tree-width. Journal of Combinatorial Theory, Series B, 58(1):22-33, 1993. Google Scholar
  28. Manuel Sorge, Mathias Weller, et al. The graph parameter hierarchy. work in progress, 2019. URL: https://manyu.pro/assets/parameter-hierarchy.pdf.
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