Can Romeo and Juliet Meet? or Rendezvous Games with Adversaries on Graphs

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 τ.

Original languageEnglish (US)
Title of host publicationGraph-Theoretic Concepts in Computer Science - 47th International Workshop, WG 2021, Revised Selected Papers
EditorsLukasz Kowalik, Michal Pilipczuk, Pawel Rzazewski
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages13
ISBN (Print)9783030868376
StatePublished - 2021
Event47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2021 - Virtual, Online
Duration: Jun 23 2021Jun 25 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12911 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2021
CityVirtual, Online


  • Complexity
  • Dynamic separators
  • Rendezvous games

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


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