We consider the cops and robber game variant consisting of one cop and onerobber on time-varying graphs (TVG) The considered TVGs are edge periodicgraphs, i.e., for each edge, a binary string $s_e$ determines in which timestep the edge is present . Thisperiodicity allows for a compact representation of the infinite TVG . We proof that even for very simple underlying graphs the problem whether a cop-winning strategy exists is NP-hard and W[1] hard parameterized by the number of vertices . Our third main resultimproves the previously known EXPTIME upper bound for Periodic Cop and Robberon general edge periodic graphs to PSPACE-membership. We also prove the previous upper bound

Author(s) : Nils Morawietz, Petra Wolf

Links : PDF - Abstract

Code :
Coursera

Keywords : edge - graphs - bound - hard - tvg -

Leave a Reply

Your email address will not be published. Required fields are marked *