Linear-Time Safe-Alternating DFS and SCCs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2016
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912534631546880 |
|---|---|
| author | Comin, Carlo Rizzi, Romeo |
| author_facet | Comin, Carlo Rizzi, Romeo |
| contents | 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 $Θ(m+n)$ linear~time. The complexity of Explicit McNaughton-Müller Games also improves from cubic to quadratic. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1610_09679 |
| institution | arXiv |
| publishDate | 2016 |
| record_format | arxiv |
| spellingShingle | Linear-Time Safe-Alternating DFS and SCCs Comin, Carlo Rizzi, Romeo Data Structures and Algorithms 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 $Θ(m+n)$ linear~time. The complexity of Explicit McNaughton-Müller Games also improves from cubic to quadratic. |
| title | Linear-Time Safe-Alternating DFS and SCCs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/1610.09679 |