Document Open Access Logo

A Timecop’s Chase Around the Table

Authors Nils Morawietz, Petra Wolf

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.77.pdf
  • Filesize: 0.78 MB
  • 18 pages

Document Identifiers

Author Details

Nils Morawietz
  • Fachbereich Mathematik und Informatik, Philipps-Universität Marburg, Germany
Petra Wolf
  • Fachbereich 4 Informatikwissenschaften, Universität Trier, Germany

Funding

  • Morawietz, Nils: {Supported by Deutsche Forschungsgemeinschaft (DFG), project OPERAH, KO 3669/5-1.}
  • Wolf, Petra: Supported by Deutsche Forschungsgemeinschaft (DFG), project FE560/9-1.

Cite AsGet BibTex

Nils Morawietz and Petra Wolf. A Timecop’s Chase Around the Table. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 77:1-77:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.MFCS.2021.77

Abstract

We consider the cops and robbers game variant consisting of one cop and one robber on time-varying graphs (TVG). The considered TVGs are edge periodic graphs, i.e., for each edge, a binary string s_e determines in which time step the edge is present, namely the edge e is present in time step t if and only if the string s_e contains a 1 at position t mod |s_e|. This periodicity allows for a compact representation of an infinite TVG. We prove that even for very simple underlying graphs, i.e., directed and undirected cycles the problem whether a cop-winning strategy exists is NP-hard and W[1]-hard parameterized by the number of vertices. Our second main result are matching lower bounds for the ratio between the length of the underlying cycle and the least common multiple (lcm) of the lengths of binary strings describing edge-periodicies over which the graph is robber-winning. Our third main result improves the previously known EXPTIME upper bound for Periodic Cop & Robber on general edge periodic graphs to PSPACE-membership.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Time variable graph
  • Edge periodic cycle
  • Game of cops and robbers
  • Computational complexity

Metrics

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

Related Versions

References

  1. Sandeep Bhadra and Afonso Ferreira. Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks. In Proceedings of the 2nd International Conference on Ad-Hoc, Mobile, and Wireless Networks, volume 2865 of Lecture Notes in Computer Science, pages 259-270. Springer, 2003. Google Scholar
  2. Niclas Boehmer, Vincent Froese, Julia Henkel, Yvonne Lasars, Rolf Niedermeier, and Malte Renken. Two influence maximization games on graphs made temporal. CoRR, abs/2105.05987, 2021. URL: http://arxiv.org/abs/2105.05987.
  3. Anthony Bonato. The game of cops and robbers on graphs. American Mathematical Soc., 2011. Google Scholar
  4. Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Time-varying graphs and dynamic networks. Int. J. Parallel Emergent Distributed Syst., 27(5):387-408, 2012. Google Scholar
  5. Nancy E. Clarke and Gary MacGillivray. Characterizations of k-copwin graphs. Discret. Math., 312(8):1421-1425, 2012. Google Scholar
  6. Luca de Alfaro, Thomas A. Henzinger, and Orna Kupferman. Concurrent reachability games. Theor. Comput. Sci., 386(3):188-217, 2007. Google Scholar
  7. Bolin Ding, Jeffrey Xu Yu, and Lu Qin. Finding time-dependent shortest paths over large graphs. In Proceedings of the 11th International Conference on Extending Database Technology, volume 261 of ACM International Conference Proceeding Series, pages 205-216. ACM, 2008. Google Scholar
  8. Thomas Erlebach and Jakob T. Spooner. A game of cops and robbers on graphs with periodic edge-connectivity. In Proceedings of 46th International Conference on Current Trends in Theory and Practice of Informatics, volume 12011 of Lecture Notes in Computer Science, pages 64-75. Springer, 2020. Google Scholar
  9. Niloy Ganguly, Andreas Deutsch, and Animesh Mukherjee. Dynamics on and of complex networks. Applications to Biology, Computer Science, and the Social Sciences, 2009. Google Scholar
  10. Petter Holme. Modern temporal network theory: a colloquium. The European Physical Journal B, 88(9):1-30, 2015. Google Scholar
  11. Petter Holme and Jari Saramäki. Temporal networks. Physics reports, 519(3):97-125, 2012. Google Scholar
  12. Neil Immerman. Number of quantifiers is better than number of tape cells. J. Comput. Syst. Sci., 22(3):384-406, 1981. Google Scholar
  13. Othon Michail and Paul G. Spirakis. Traveling salesman problems in temporal graphs. Theor. Comput. Sci., 634:1-23, 2016. Google Scholar
  14. Nils Morawietz, Carolin Rehs, and Mathias Weller. A timecop’s work is harder than you think. In Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, volume 170 of LIPIcs, pages 71:1-71:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  15. Richard J. Nowakowski and Peter Winkler. Vertex-to-vertex pursuit in a graph. Discret. Math., 43(2-3):235-239, 1983. Google Scholar
  16. Alain Quilliot. Jeux et pointes fixes sur les graphes. PhD thesis, Ph. D. Dissertation, Université de Paris VI, 1978. Google Scholar
  17. Klaus Sutner and Wolfgang Maass. Motion planning among time dependent obstacles. Acta Informatica, 26(1-2):93-122, 1988. Google Scholar
  18. Klaus Wehmuth, Artur Ziviani, and Eric Fleury. A unifying model for representing time-varying graphs. In 2015 IEEE International Conference on Data Science and Advanced Analytics, DSAA 2015, Campus des Cordeliers, Paris, France, October 19-21, 2015, pages 1-10. IEEE, 2015. Google Scholar
  19. Zhensheng Zhang. Routing in intermittently connected mobile ad hoc networks and delay tolerant networks: Overview and challenges. IEEE Commun. Surv. Tutorials, 8(1-4):24-37, 2006. 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