2026-07-31T06:50:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20610 2024-08-23T05:50:29Z ddc:004 open_access

Romeo and Juliet Is EXPTIME-Complete Gahlawat, Harmender Křišťan, Jan Matyáš Valla, Tomáš Rendezvous Games on graphs EXPTIME-completeness Dynamic Separators 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Harmender Gahlawat and Jan Matyáš Křišťan and Tomáš Valla 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.54 urn:nbn:de:0030-drops-206106 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.54 eng https://creativecommons.org/licenses/by/4.0/legalcode