Title: 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 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.