ARRIVAL: Next stop in CLS

Bernd Gärtner; Thomas Dueholm Hansen; Pavel Hubácek; Karel Král; Hagar Mosaad; Veronika Slívová

doi:10.4230/LIPIcs.ICALP.2018.60

ARRIVAL: Next stop in CLS

Bernd Gärtner, Thomas Dueholm Hansen, Pavel Hubácek, Karel Král, Hagar Mosaad, Veronika Slívová

Department of Computer Science

4 Citations (Scopus)

9 Downloads (Pure)

Abstract

We study the computational complexity of Arrival, a zero-player game on n-vertex switch graphs introduced by Dohrau, Gärtner, Kohler, Matoušek, and Welzl. They showed that the problem of deciding termination of this game is contained in NP ∩ coNP. Karthik C. S. recently introduced a search variant of Arrival and showed that it is in the complexity class PLS. In this work, we significantly improve the known upper bounds for both the decision and the search variants of Arrival. First, we resolve a question suggested by Dohrau et al. and show that the decision variant of Arrival is in UP ∩ coUP. Second, we prove that the search variant of Arrival is contained in CLS. Third, we give a randomized O(1.4143ⁿ)-time algorithm to solve both variants. Our main technical contributions are (a) an e ciently verifiable characterization of the unique witness for termination of the Arrival game, and (b) an e cient way of sampling from the state space of the game. We show that the problem of finding the unique witness is contained in CLS, whereas it was previously conjectured to be FPSPACE-complete. The e cient sampling procedure yields the first algorithm for the problem that has expected runtime O(cⁿ) with c < 2.

Original language	English
Title of host publication	45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
Editors	Ioannis Chatzigiannakis , Christos Kaklamanis, Da}niel Marx, Donald Sannella
Number of pages	13
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication date	2018
Article number	60
ISBN (Electronic)	9783959770767
DOIs	https://doi.org/10.4230/LIPIcs.ICALP.2018.60
Publication status	Published - 2018
Event	45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 - Prague, Czech Republic Duration: 9 Jul 2018 → 13 Jul 2018

Conference

Conference	45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
Country/Territory	Czech Republic
City	Prague
Period	09/07/2018 → 13/07/2018
Sponsor	Avast, RSJ

Series	Leibniz International Proceedings in Informatics, LIPIcs
Volume	107
ISSN	1868-8969

Keywords

CLS
Switch graphs
UP ∩ coUP
Zero-player game

Access to Document

10.4230/LIPIcs.ICALP.2018.60Licence: CC BY

ARRIVAL Next Stop in CLSFinal published version, 588 KBLicence: CC BY

Cite this

Gärtner, B., Hansen, T. D., Hubácek, P., Král, K., Mosaad, H., & Slívová, V. (2018). ARRIVAL: Next stop in CLS. In I. Chatzigiannakis , C. Kaklamanis, D. Marx, & D. Sannella (Eds.), 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 [60] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs Vol. 107 https://doi.org/10.4230/LIPIcs.ICALP.2018.60

ARRIVAL : Next stop in CLS. / Gärtner, Bernd; Hansen, Thomas Dueholm; Hubácek, Pavel et al.

45th International Colloquium on Automata, Languages, and Programming, ICALP 2018. ed. / Ioannis Chatzigiannakis ; Christos Kaklamanis; Da}niel Marx; Donald Sannella. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018. 60 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 107).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Gärtner, B, Hansen, TD, Hubácek, P, Král, K, Mosaad, H & Slívová, V 2018, ARRIVAL: Next stop in CLS. in I Chatzigiannakis , C Kaklamanis, D Marx & D Sannella (eds), 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018., 60, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, vol. 107, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, Prague, Czech Republic, 09/07/2018. https://doi.org/10.4230/LIPIcs.ICALP.2018.60

Gärtner B, Hansen TD, Hubácek P, Král K, Mosaad H, Slívová V. ARRIVAL: Next stop in CLS. In Chatzigiannakis I, Kaklamanis C, Marx D, Sannella D, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2018. 60. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 107). doi: 10.4230/LIPIcs.ICALP.2018.60

Gärtner, Bernd ; Hansen, Thomas Dueholm ; Hubácek, Pavel et al. / ARRIVAL : Next stop in CLS. 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018. editor / Ioannis Chatzigiannakis ; Christos Kaklamanis ; Da}niel Marx ; Donald Sannella. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 107).

@inproceedings{b7284c13797d42fc93825959b876f06c,

title = "ARRIVAL: Next stop in CLS",

abstract = "We study the computational complexity of Arrival, a zero-player game on n-vertex switch graphs introduced by Dohrau, G{\"a}rtner, Kohler, Matou{\v s}ek, and Welzl. They showed that the problem of deciding termination of this game is contained in NP ∩ coNP. Karthik C. S. recently introduced a search variant of Arrival and showed that it is in the complexity class PLS. In this work, we significantly improve the known upper bounds for both the decision and the search variants of Arrival. First, we resolve a question suggested by Dohrau et al. and show that the decision variant of Arrival is in UP ∩ coUP. Second, we prove that the search variant of Arrival is contained in CLS. Third, we give a randomized O(1.4143n)-time algorithm to solve both variants. Our main technical contributions are (a) an e ciently verifiable characterization of the unique witness for termination of the Arrival game, and (b) an e cient way of sampling from the state space of the game. We show that the problem of finding the unique witness is contained in CLS, whereas it was previously conjectured to be FPSPACE-complete. The e cient sampling procedure yields the first algorithm for the problem that has expected runtime O(cn) with c < 2.",

keywords = "CLS, Switch graphs, UP ∩ coUP, Zero-player game",

author = "Bernd G{\"a}rtner and Hansen, {Thomas Dueholm} and Pavel Hub{\'a}cek and Karel Kr{\'a}l and Hagar Mosaad and Veronika Sl{\'i}vov{\'a}",

year = "2018",

doi = "10.4230/LIPIcs.ICALP.2018.60",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "{Chatzigiannakis }, {Ioannis } and Kaklamanis, {Christos } and Da}niel Marx and Donald Sannella",

booktitle = "45th International Colloquium on Automata, Languages, and Programming, ICALP 2018",

note = "45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 ; Conference date: 09-07-2018 Through 13-07-2018",

}

TY - GEN

T1 - ARRIVAL

T2 - 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018

AU - Gärtner, Bernd

AU - Hansen, Thomas Dueholm

AU - Hubácek, Pavel

AU - Král, Karel

AU - Mosaad, Hagar

AU - Slívová, Veronika

PY - 2018

Y1 - 2018

N2 - We study the computational complexity of Arrival, a zero-player game on n-vertex switch graphs introduced by Dohrau, Gärtner, Kohler, Matoušek, and Welzl. They showed that the problem of deciding termination of this game is contained in NP ∩ coNP. Karthik C. S. recently introduced a search variant of Arrival and showed that it is in the complexity class PLS. In this work, we significantly improve the known upper bounds for both the decision and the search variants of Arrival. First, we resolve a question suggested by Dohrau et al. and show that the decision variant of Arrival is in UP ∩ coUP. Second, we prove that the search variant of Arrival is contained in CLS. Third, we give a randomized O(1.4143n)-time algorithm to solve both variants. Our main technical contributions are (a) an e ciently verifiable characterization of the unique witness for termination of the Arrival game, and (b) an e cient way of sampling from the state space of the game. We show that the problem of finding the unique witness is contained in CLS, whereas it was previously conjectured to be FPSPACE-complete. The e cient sampling procedure yields the first algorithm for the problem that has expected runtime O(cn) with c < 2.

AB - We study the computational complexity of Arrival, a zero-player game on n-vertex switch graphs introduced by Dohrau, Gärtner, Kohler, Matoušek, and Welzl. They showed that the problem of deciding termination of this game is contained in NP ∩ coNP. Karthik C. S. recently introduced a search variant of Arrival and showed that it is in the complexity class PLS. In this work, we significantly improve the known upper bounds for both the decision and the search variants of Arrival. First, we resolve a question suggested by Dohrau et al. and show that the decision variant of Arrival is in UP ∩ coUP. Second, we prove that the search variant of Arrival is contained in CLS. Third, we give a randomized O(1.4143n)-time algorithm to solve both variants. Our main technical contributions are (a) an e ciently verifiable characterization of the unique witness for termination of the Arrival game, and (b) an e cient way of sampling from the state space of the game. We show that the problem of finding the unique witness is contained in CLS, whereas it was previously conjectured to be FPSPACE-complete. The e cient sampling procedure yields the first algorithm for the problem that has expected runtime O(cn) with c < 2.

KW - CLS

KW - Switch graphs

KW - UP ∩ coUP

KW - Zero-player game

UR - http://www.scopus.com/inward/record.url?scp=85049804503&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ICALP.2018.60

DO - 10.4230/LIPIcs.ICALP.2018.60

M3 - Article in proceedings

AN - SCOPUS:85049804503

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018

A2 - Chatzigiannakis , Ioannis

A2 - Kaklamanis, Christos

A2 - Marx, Da}niel

A2 - Sannella, Donald

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

Y2 - 9 July 2018 through 13 July 2018

ER -

ARRIVAL: Next stop in CLS

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this