License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.90
URN: urn:nbn:de:0030-drops-74941
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7494/
Bonnet, Édouard ;
Gaspers, Serge ;
Lambilliotte, Antonin ;
Rümmele, Stefan ;
Saffidine, Abdallah
The Parameterized Complexity of Positional Games
Abstract
We study the parameterized complexity of several positional games. Our main result is that Short Generalized Hex is W[1]-complete parameterized by the number of moves. This solves an open problem from Downey and Fellows’ influential list of open problems from 1999. Previously, the problem was thought of as a natural candidate for AW[*]-completeness. Our main tool is a new fragment of first-order logic where universally quantified variables only occur in inequalities. We show that model-checking on arbitrary relational structures for a formula in this fragment is W[1]-complete when parameterized by formula size. We also consider a general framework where a positional game is represented as a hypergraph and two players alternately pick vertices. In a Maker-Maker game, the first player to have picked all the vertices of some hyperedge wins the game. In a Maker-Breaker game, the first player wins if she picks all the vertices of some hyperedge, and the second player wins otherwise. In an Enforcer-Avoider game, the first player wins if the second player picks all the vertices of some hyperedge, and the second player wins otherwise. Short Maker-Maker, Short Maker-Breaker, and Short Enforcer-Avoider are respectively AW[*]-, W[1]-, and co-W[1]-complete parameterized by the number of moves. This suggests a rough parameterized complexity categorization into positional games that are complete for the first level of the W-hierarchy when the winning condition only depends on which vertices one player has been able to pick, but AW[*]-complete when it depends on which vertices both players have picked. However, some positional games with highly structured board and winning configurations are fixed-parameter tractable. We give another example of such a game, Short k-Connect, which is fixed-parameter tractable when parameterized by the number of moves.
BibTeX - Entry
@InProceedings{bonnet_et_al:LIPIcs:2017:7494,
author = {{\'E}douard Bonnet and Serge Gaspers and Antonin Lambilliotte and Stefan R{\"u}mmele and Abdallah Saffidine},
title = {{The Parameterized Complexity of Positional Games}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {90:1--90:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-041-5},
ISSN = {1868-8969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7494},
URN = {urn:nbn:de:0030-drops-74941},
doi = {10.4230/LIPIcs.ICALP.2017.90},
annote = {Keywords: Hex, Maker-Maker games, Maker-Breaker games, Enforcer-Avoider games, parameterized complexity theory}
}
|
Keywords: |
|
Hex, Maker-Maker games, Maker-Breaker games, Enforcer-Avoider games, parameterized complexity theory |
|
Collection: |
|
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
07.07.2017 |
