The parameterized complexity of positional games

Conference paper


Bonnet, E., Gaspers, S., Lambilliotte, A., Rümmele, S. and Saffidine, A. 2017. The parameterized complexity of positional games. 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Warsaw, Poland 10 - 14 Jul 2017 LIPICS Schloss Dagstuhl. pp. 90: 1-90: 14 https://doi.org/10.4230/LIPIcs.ICALP.2017.90
TypeConference paper
TitleThe parameterized complexity of positional games
AuthorsBonnet, E., Gaspers, S., Lambilliotte, A., Rümmele, S. and Saffidine, A.
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.

LanguageEnglish
Conference44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Page range90: 1-90: 14
ISSN1868-8969
ISBN
Hardcover9783959770415
PublisherLIPICS Schloss Dagstuhl
Publication dates
PrintJul 2017
Publication process dates
Deposited23 Apr 2018
Accepted14 Apr 2017
Output statusPublished
Publisher's version
License
Additional information

Article number = 90

Digital Object Identifier (DOI)https://doi.org/10.4230/LIPIcs.ICALP.2017.90
Book title44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Permalink -

https://repository.mdx.ac.uk/item/879xz

Download files


Publisher's version
  • 9
    total views
  • 2
    total downloads
  • 2
    views this month
  • 1
    downloads this month

Export as