Search

• < Previous
• 1
• Next >

---

Time and Parallelizability Results for Parity Games with Bounded Tree and DAG Width

John Fearnley ; Sven Schewe.

Parity games are a much researched class of games in NP intersect CoNP that are not known to be in P. Consequently, researchers have considered specialised algorithms for the case where certain graph parameters are small. In this paper, we study parity games on graphs with bounded treewidth, and&nbsp;[&hellip;]

---

The Complexity of All-switches Strategy Improvement

John Fearnley ; Rahul Savani.

Strategy improvement is a widely-used and well-studied class of algorithms for solving graph-based infinite games. These algorithms are parameterized by a switching rule, and one of the most natural rules is "all switches" which switches as many edges as possible in each iteration. Continuing a&nbsp;[&hellip;]

---

Reachability Switching Games

John Fearnley ; Martin Gairing ; Matthias Mnich ; Rahul Savani.

We study the problem of deciding the winner of reachability switching games for zero-, one-, and two-player variants. Switching games provide a deterministic analogue of stochastic games. We show that the zero-player case is NL-hard, the one-player case is NP-complete, and that the two-player case&nbsp;[&hellip;]

---