Romeo and Juliet Is EXPTIME-Complete
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F24%3A00379999" target="_blank" >RIV/68407700:21240/24:00379999 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.4230/LIPIcs.MFCS.2024.54" target="_blank" >https://doi.org/10.4230/LIPIcs.MFCS.2024.54</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.MFCS.2024.54" target="_blank" >10.4230/LIPIcs.MFCS.2024.54</a>
Alternative languages
Result language
angličtina
Original language name
Romeo and Juliet Is EXPTIME-Complete
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA24-12046S" target="_blank" >GA24-12046S: Computing and Approximating Equilibria in Games With Complex Strategy Spaces</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2024
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science
ISBN
978-3-95977-335-5
ISSN
1868-8969
e-ISSN
—
Number of pages
16
Pages from-to
"54:1"-"54:16"
Publisher name
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Place of publication
—
Event location
Bratislava
Event date
Aug 26, 2024
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—