Open in viewer

Open access

Author

Wolleb-Graf, Daniel

Date

2018-12Type

- Doctoral Thesis

ETH Bibliography

yes
Altmetrics

Open in viewer

Abstract

Take a blank page, draw some small circles, and connect them with a few arrows, and voilà you created a directed graph, a digraph for short. Now let us ask an algorithmic question: If I point out two of those circles to you, one as the start and one as the target, can you find a way to go from the start to the target by only using the arrows in their one-way direction? While this reachability question is well-studied, we found new algorithms for the following slight variations of the reachability problem:
- What if we ask this questions for many starts and many targets while we also add and remove arrows in between answering these questions?
- What if we want to find two ways from the start to the target that use completely different arrows? Or can we even find three disjoint paths? And how fast can we compute the answer for all combinations of starts and targets?
For the dynamic reachability problem, we review the link-cut tree data structure for dynamic rooted forests before we extend it to a new class of dynamic graphs: partial-function graphs. We provide algorithms for arbitrarily interleaved queries and updates to the graph in time O(log n).
In the generalized reachability problem, we ask about the existence of multiple arc-disjoint paths between the query vertices. The all-pairs k-reachability problem asks for the number of arc-disjoint paths between all vertex pairs, where one can answer 'at least k', whenever there are k or more arc-disjoint paths.
2-reachability answers basic resilience of paths, i.e., is there an arc that can not be avoided on the path from u to v. As our main result, we present an algorithm running in time O(n^ω log n) to compute all-pairs 2-reachability of any digraph, where ω is the matrix multiplication exponent. This result comes in three steps: first, we develop a path algebra with binary encodings for acyclic graphs, second, we use dominator trees to build auxiliary graphs that represent the answer for strongly connected graphs, and third, we carefully combine the two on arbitrary digraphs.
Finally, we look at the general k-reachability problem restricted to acyclic graphs. We develop a framework dealing with the structure of extremal cuts and encoding and handling those cuts efficiently to come up with two algorithms for DAGs: one running in time O(mn^{1+o(1)}) for k = o(√{log n}) and one in time O(n^{ω + o(1)}) for k = o(log log n). One nice side effect of these algorithms is that they do not only report the size of the minimum cut but also provide a cut as a witness Show more

Permanent link

https://doi.org/10.3929/ethz-b-000321834Publication status

publishedExternal links

Search via SFX
Contributors

Examiner: Widmayer, PeterExaminer: Hromkovič, Juraj

Examiner: Italiano, Giuseppe F.

Publisher

ETH ZurichSubject

Digraph; Reachability; Link-Cut Trees; Extremal Cuts; Fast Matrix MultiplicationOrganisational unit

03340 - Widmayer, Peter (emeritus) / Widmayer, Peter (emeritus)
More

Show all metadata
ETH Bibliography

yes
Altmetrics