License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2021.77
URN: urn:nbn:de:0030-drops-145176
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14517/
Go to the corresponding LIPIcs Volume Portal

Morawietz, Nils ; Wolf, Petra

A Timecop’s Chase Around the Table

pdf-format:
LIPIcs-MFCS-2021-77.pdf (0.8 MB)

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.

BibTeX - Entry

@InProceedings{morawietz_et_al:LIPIcs.MFCS.2021.77,
  author =	{Morawietz, Nils and Wolf, Petra},
  title =	{{A Timecop’s Chase Around the Table}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{77:1--77:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14517},
  URN =		{urn:nbn:de:0030-drops-145176},
  doi =		{10.4230/LIPIcs.MFCS.2021.77},
  annote =	{Keywords: Time variable graph, Edge periodic cycle, Game of cops and robbers, Computational complexity}
}

Keywords: Time variable graph, Edge periodic cycle, Game of cops and robbers, Computational complexity
Collection: 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Issue Date: 2021
Date of publication: 18.08.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI