Romeo and Juliet Is EXPTIME-Complete

Harmender Gahlawat, Jan Matyás Kristan, Tomás VallaMFCS 2024 · OpenReview

TL;DR

This paper proves that the "Romeo and Juliet" game, a graph-based pursuit-evasion scenario where two agents try to meet while evading adversaries, is EXPTIME-complete for both undirected and directed graphs. This resolves a long-standing conjecture and establishes a high complexity bound for this intriguing game.

What Problem Does This Paper Address?

The paper tackles the computational complexity of the "Romeo and Juliet" game. This game involves two players: a facilitator controlling two agents, Romeo (R) and Juliet (J), who want to meet at a vertex in a graph, and a divider player controlling $k$ adversaries. The divider's goal is to prevent R and J from ever meeting. The core question is: given a graph, starting positions for R and J, and a number $k$ of dividers, can the facilitator guarantee a meeting? This is related to the concept of the "dynamic separation number," which is the minimum number of dividers needed to prevent a meeting. While previous work showed the game is PSPACE-hard, this paper aims to settle whether it's EXPTIME-complete, a significantly harder complexity class.

Methods

The paper establishes the EXPTIME-completeness of the Romeo and Juliet game through reductions from known EXPTIME-complete problems.

  • Undirected Graphs: The primary technique is a non-trivial reduction from the "GUARDUNDIR" game (a guarding game on undirected graphs) to the Romeo and Juliet game. This involves constructing a new graph for Romeo and Juliet by creating multiple copies of the original graph's regions and carefully connecting them with "secret gardens" and "bridges." These gadgets are designed to mimic the dynamics of the guarding game, ensuring that if the cops have a winning strategy in the original game, the dividers will have a winning strategy in the constructed Romeo and Juliet game, and vice-versa.
  • Directed Graphs: For directed graphs, the reduction is more straightforward, from the "GUARD" game (the directed version of the guarding game) to Romeo and Juliet on directed graphs. This construction is simpler and leverages the directed nature of the graph.
  • Directed Acyclic Graphs (DAGs): For DAGs, the paper shows the game is PSPACE-complete and co-W[2]-hard. This is achieved by defining a "RELAXED ROMEO AND JULIET" game and using it to translate hardness results from "ROMEO AND JULIET IN TIME" on general graphs to DAGs.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • EXPTIME-Completeness Resolution: The paper definitively proves that Romeo and Juliet is EXPTIME-complete, resolving a conjecture and placing it at a high point in computational complexity for graph games.
  • Sophisticated Graph Construction: The reduction from GUARDUNDIR to Romeo and Juliet on undirected graphs is a key technical contribution. The construction of "secret gardens" and "bridges" is a clever way to translate the cop-robber dynamics into the Romeo and Juliet framework.
  • Divergent Complexity on DAGs: The finding that the game's complexity drops to PSPACE-complete on DAGs, while remaining EXPTIME-complete for general directed graphs, highlights how graph structure can significantly impact computational hardness.
  • Connection to Graph Searching: The paper firmly places Romeo and Juliet within the broader context of graph searching games, drawing parallels and reductions from established problems like the guarding game.

Key Results

  • Theorem 1: ROMEO AND JULIET is EXPTIME-complete for undirected graphs.
  • Theorem 2: ROMEO AND JULIET is EXPTIME-complete for directed (oriented) graphs.
  • Theorem 3: ROMEO AND JULIET is PSPACE-complete when restricted to directed acyclic graphs (DAGs).
  • Theorem 4: ROMEO AND JULIET is co-W[2]-hard parameterized by $k$ when restricted to DAGs.

Limitations and Future Work

  • Planar Graphs and Surfaces: The paper notes that the dynamic separation number for planar graphs can be unbounded, and it would be interesting to determine the computational complexity of Romeo and Juliet on planar graphs and graphs on surfaces.
  • EXPTIME-Completeness of "Romeo and Juliet in Time": The authors suggest it would be interesting to investigate if "Romeo and Juliet in Time" (a variant where meeting must occur within a certain number of rounds) is also EXPTIME-complete, as conjectured.
  • Lower Bounds: Extending the known lower bound of $2^{\Omega(k \log n)}$ for solving Romeo and Juliet to $2^{\Omega(n)}$ would be a significant theoretical advancement.

Summary updated

Abstract

Romeo and Juliet is a two player Rendezvous game played on graphs where one player controls two agents, Romeo (ℛ) and Juliet (𝒥) who aim to meet at a vertex against k adversaries, called dividers, controlled by the other player. The optimization in this game lies at deciding the minimum number of dividers sufficient to restrict ℛ and 𝒥 from meeting in a graph, called the dynamic separation number. We establish that Romeo and Juliet is EXPTIME-complete, settling a conjecture of Fomin, Golovach, and Thilikos [Inf. and Comp., 2023] positively. We also consider the game for directed graphs and establish that although the game is EXPTIME-complete for general directed graphs, it is PSPACE-complete and co-W[2]-hard for directed acyclic graphs.
BibTeX
@inproceedings{gahlawat2024romeo,
  author = {Harmender Gahlawat and Jan Matyás Kristan and Tomás Valla},
  title = {{Romeo and Juliet Is EXPTIME-Complete}},
  booktitle = {MFCS},
  year = {2024},
  url = {https://openreview.net/forum?id=YL2WjEtoFq},
}
Figure