Short Maker-Maker, Short Maker-Breaker, and Short Enforcer-Avoider are respectively AW-, W-, and co-W-complete parameterized by the number of moves. 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. 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 a Maker-Maker game, the first player to have picked all the vertices of some hyperedge wins the game. We also consider a general framework where a positional game is represented as a hypergraph and two players alternately pick vertices. We show that model-checking on arbitrary relational structures for a formula in this fragment is W-complete when parameterized by formula size. Our main tool is a new fragment of first-order logic where universally quantified variables only occur in inequalities. Previously, the problem was thought of as a natural candidate for AW-completeness. This solves an open problem from Downey and Fellows’ influential list of open problems from 1999. Our main result is that Short Generalized Hex is W-complete parameterized by the number of moves. We study the parameterized complexity of several positional games.
0 kommentar(er)
