PSPACE-completeness conjecture for Fast-Strategy on bipartite graphs

Let GG be a bipartite graph, and let tt denote the number of guards in the eternal domination game. The decision problem \textscFastStrategy\textsc{Fast-Strategy} asks whether the guards have a strategy satisfying the fast-winning condition on GG. Fast-Strategy conjecture. The problem \textscFastStrategy\textsc{Fast-Strategy} is PSPACE-complete on bipartite graphs. This conjecture is motivated by the PSPACE-hardness results for related graph classes and by the frequent dichotomy between polynomial-time solvability and PSPACE-hardness in game problems; the completeness of Fast-Strategy on bipartite graphs remains open.

Sources & referencesView supporting material

Primary source

Guillaume Bagan, Nicolas Bousquet, Nacim Oijid and Théo Pierron, “Fast winning strategies for the attacker in eternal domination”, arXiv:2401.10584 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.