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