TY - GEN
T1 - Can Romeo and Juliet Meet? or Rendezvous Games with Adversaries on Graphs
AU - Fomin, Fedor V.
AU - Golovach, Petr A.
AU - Thilikos, Dimitrios M.
N1 - Publisher Copyright:
© 2021, Springer Nature Switzerland AG.
PY - 2021
Y1 - 2021
N2 - We introduce the rendezvous game with adversaries. In this game, two players, Facilitator and Divider, play against each other on a graph. Facilitator has two agents, and Divider has a team of k agents located in some vertices of the graph. They take turns in moving their agents to adjacent vertices (or staying put). Facilitator wins if his agents meet in some vertex of the graph. The goal of Divider is to prevent the rendezvous of Facilitator’s agents. Our interest is to decide whether Facilitator can win. It appears that, in general, the problem is PSPACE -hard and, when parameterized by k, co- W[ 2 ] -hard. Moreover, even the game’s variant where we ask whether Facilitator can ensure the meeting of his agents within τ steps is co- NP -complete already for τ= 2. On the other hand, for chordal and P5 -free graphs, we prove that the problem is solvable in polynomial time. These algorithms exploit an interesting relation of the game and minimum vertex cuts in certain graph classes. Finally, we show that the problem is fixed-parameter tractable parameterized by both the graph’s neighborhood diversity and τ.
AB - We introduce the rendezvous game with adversaries. In this game, two players, Facilitator and Divider, play against each other on a graph. Facilitator has two agents, and Divider has a team of k agents located in some vertices of the graph. They take turns in moving their agents to adjacent vertices (or staying put). Facilitator wins if his agents meet in some vertex of the graph. The goal of Divider is to prevent the rendezvous of Facilitator’s agents. Our interest is to decide whether Facilitator can win. It appears that, in general, the problem is PSPACE -hard and, when parameterized by k, co- W[ 2 ] -hard. Moreover, even the game’s variant where we ask whether Facilitator can ensure the meeting of his agents within τ steps is co- NP -complete already for τ= 2. On the other hand, for chordal and P5 -free graphs, we prove that the problem is solvable in polynomial time. These algorithms exploit an interesting relation of the game and minimum vertex cuts in certain graph classes. Finally, we show that the problem is fixed-parameter tractable parameterized by both the graph’s neighborhood diversity and τ.
KW - Complexity
KW - Dynamic separators
KW - Rendezvous games
UR - http://www.scopus.com/inward/record.url?scp=85115868606&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85115868606&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-86838-3_24
DO - 10.1007/978-3-030-86838-3_24
M3 - Conference contribution
AN - SCOPUS:85115868606
SN - 9783030868376
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 308
EP - 320
BT - Graph-Theoretic Concepts in Computer Science - 47th International Workshop, WG 2021, Revised Selected Papers
A2 - Kowalik, Lukasz
A2 - Pilipczuk, Michal
A2 - Rzazewski, Pawel
PB - Springer Science and Business Media Deutschland GmbH
T2 - 47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2021
Y2 - 23 June 2021 through 25 June 2021
ER -