PSPACE-completeness conjecture for Fast-Strategy on bipartite graphs
PSPACE-completeness conjecture for Fast-Strategy on bipartite graphs
Let be a bipartite graph, and let denote the number of guards in the eternal domination game. The decision problem asks whether the guards have a strategy satisfying the fast-winning condition on . Fast-Strategy conjecture. The problem 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.