The parameterized complexity of positional games

DOI10.4230/LIPICS.ICALP.2017.90MaRDI QIDQ5111422zbMATH OpenOpenAlexFDO

Authors Édouard Bonnet, Serge Gaspers, Antonin Lambilliotte, Stefan Rümmele, Abdallah Saffidine

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1704.08536

zbMATH Keywords

maker-breaker gameshexparameterized complexity theoryenforcer-avoider gamesmaker-maker games

Mathematics Subject Classification ID

Positional games (pursuit and evasion, etc.) (91A24) Combinatorial games (91A46) Parameterized complexity, tractability and kernelization (68Q27) Algorithmic game theory and complexity (91A68)

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.

Recommendations

• Parameterized Chess
• On the complexity of connection games
• On the complexity of chooser-picker positional games
• The complexity of poset games
• Weak positional games on hypergraphs

Cited in

(13)

• scientific article; zbMATH DE number 1948167 (Why is no real title available?)
• scientific article; zbMATH DE number 7447732 (Why is no real title available?)
• On the Complexity of n-Player Hackenbush
• Complexity of maker-breaker games on edge sets of graphs
• scientific article; zbMATH DE number 7075886 (Why is no real title available?)
• The Game of n-Player Shove and Its Complexity
• The Rabin index of parity games: its complexity and approximation
• Upper bounds on positional Paris-Harrington games
• On the complexity of connection games
• On the complexity of computing winning strategies for finite poset games
• On the fairness and complexity of generalized \(k\)-in-a-row games
• The maker-maker domination game in forests
• Parameterized Chess

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)