Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs

Fedor V. Fomin, Petr A. Golovach, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review

Abstract

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. They take turns in moving their agents to adjacent vertices (or staying put). Facilitator wins if his agents meet in some vertex. Divider aims to prevent the rendezvous of Facilitator's agents. We show that deciding whether Facilitator can win is PSPACE-hard and, when parameterized by k, co-W[2]-hard. Moreover, even deciding whether Facilitator can win 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. Finally, we show that the problem is fixed-parameter tractable parameterized by both the graph's neighborhood diversity and the number of steps τ.

Original languageEnglish (US)
Article number105049
JournalInformation and Computation
Volume293
DOIs
StatePublished - Aug 2023

Keywords

  • Complexity
  • Dynamic separators
  • Rendezvous games

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs'. Together they form a unique fingerprint.

Cite this