### Page Content

### to Navigation

# The Parameterized Complexity of Positional Games

**Abdallah Saffidine (University of New South Wales)**

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.

This is joint work with Édouard Bonnet, Serge Gaspers, Antonin Lambilliotte, and Stefan Rümmele (ICALP 2017).

Date | Speaker | Location | Language |
---|---|---|---|

11.05.2017 16:15 | Abdallah Saffidine | TEL 512 | English |