An alternating graph is a directed graph whose vertex set is partitioned into two classes, existential and universal. This forms the basic arena for a plethora of infinite duration two-player games where Player~$\square$ and~$\ocircle$ alternate in a turn-based sliding of a pebble along the arcs they control. We study alternating strongly-connectedness as a generalization of strongly-connectedness in directed graphs, aiming at providing a linear time decomposition and a sound structural graph characterization. For this a refined notion of alternating reachability is introduced: Player~$\square$ attempts to reach vertices without leaving a prescribed subset of the vertices, while Player~$\ocircle$ works against. This is named \emph{safe alternating reachability}. It is shown that every arena uniquely decomposes into safe alternating strongly-connected components where Player~$\square$ can visit each vertex within a given component infinitely often, without having to ever leave out the component itself. Our main result is a linear time algorithm for computing this alternating graph decomposition. Both the underlying graph structures and the algorithm generalize the classical decomposition of a directed graph into strongly-connected components. The algorithm builds on a linear time generalization of the depth-first search on alternation, taking inspiration from Tarjan 1972 machinery. Our theory has direct applications in solving well-known infinite duration pebble games faster. Dinneen and Khoussainov showed in 1999 that deciding a given Update Game costs $O(mn)$ time, where $n$ is the number of vertices and $m$ is that of arcs. We solve the task in $\Theta(m+n)$ linear~time. The complexity of Explicit McNaughton-M\"uller Games also improves from cubic to quadratic.

Thanks. We have received your report. If we find this content to be in
violation of our guidelines,
we will remove it.

Ok