The Parameterized Complexity of Positional Games
From MaRDI portal
Publication:5111422
DOI10.4230/LIPICS.ICALP.2017.90zbMATH Open1447.91027arXiv1704.08536OpenAlexW2962896135MaRDI QIDQ5111422FDOQ5111422
Abdallah Saffidine, Édouard Bonnet, Antonin Lambilliotte, Serge Gaspers, Stefan Rümmele
Publication date: 27 May 2020
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 is AW[*]-complete, whereas Short Maker-Breaker is W[1]-complete and Short Enforcer-Avoider 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 configurations only depend on which vertices one player has been able to pick, but AW[*]-completeness when the winning condition depends on which vertices both players have picked. However, some positional games where the board and the winning configurations are highly structured 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.
Full work available at URL: https://arxiv.org/abs/1704.08536
Positional games (pursuit and evasion, etc.) (91A24) Combinatorial games (91A46) Parameterized complexity, tractability and kernelization (68Q27) Algorithmic game theory and complexity (91A68)
Cited In (10)
- Title not available (Why is that?)
- On the complexity of computing winning strategies for finite poset games
- Upper bounds on positional Paris-Harrington games
- The Rabin index of parity games: its complexity and approximation
- Complexity of maker-breaker games on edge sets of graphs
- Title not available (Why is that?)
- On the Complexity of n-Player Hackenbush
- The maker-maker domination game in forests
- Title not available (Why is that?)
- The Game of n-Player Shove and Its Complexity
This page was built for publication: The Parameterized Complexity of Positional Games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111422)
