<p>I think the best results so far are discussed in <a href="http://arxiv.org/abs/cs.DS/0104001" rel="nofollow">"Mantaining Dynamic Matrices for Fully Dynamic Transitive Closure"</a>. That paper discusses a randomized algorithm with $O(n^{0.58})$ query time and an $O(n^{1.58})$ update time.</p>

<p>(This only covers the first version of your question, with <code>link</code> and <code>unlink</code> but without <code>add</code> and <code>remove</code>.)</p>

CC BY-SA 3.0
2011-06-19T22:46:22.300Z
The bounds are build on Strassen's algorithm though, so the constant is huge.
Thomas Ahle
CC BY-SA 2.5
2011-02-27T00:49:00.417Z
2011-02-27T00:49:00.417Z
jbapple
<p>The problem you have described is fully dynamic DAG reachability (also referred to as fully dynamic transitive closure on DAGs).
It's called fully dynamic since people also study the versions where only deletions are possible (then it's called decremental reachability), and where only insertions are possible (called incremental reachability).</p>

<p>There are a few tradeoffs between the update time and the query time. Let $m$ be the number of edges and $n$ the number of vertices.
For DAGs, Demetrescu and Italiano (FOCS'00) gave a randomized data structure which supports updates (edge inserts or deletes) in O($n^{1.58}$) time and reachability queries in O($n^{0.58}$) time (node inserts/deletes are also supported, in O(1) time); this result was extended by Sankowski (FOCS'04) to work for general directed graphs. Also for DAGs, Roditty (SODA'03) showed that you can maintain the transitive closure matrix in total time O($mn+I·n^2+D$), where $I$ is the number of insertions, $D$ the number of deletions and of course the query time is O($1$).</p>

<p>For general directed graphs, the following (update, query) times are known:
(O($n^2$), O(1)) (Demetrescu and Italiano FOCS'00 (amortized), Sankowski FOCS'04 (worst case)), (O($m\sqrt{n}$), $O(\sqrt{n}$)) (Roditty, Zwick FOCS'02), (O($m+n\log n$), O($n$)) (Roditty, Zwick STOC'04), (O($n^{1.58}$),O($n^{0.58}$)) and (O($n^{1.495}$),O($n^{1.495}$)) by Sankowski (FOCS'04). </p>

<p>Obtaining a polylogarithmic query time, without increasing the update time too much is a major open problem, even for DAGs. </p>

CC BY-SA 2.5
2011-02-27T05:43:48.840Z
Thank you for your answer. Although I have to say I'm disappointed at how poor those bounds are. :(
Justin Kilpatrick
CC BY-SA 2.5
2011-02-27T05:59:16.460Z
A related question: could you point me toward any references on the simpler problems, incremental reachability, and decremental reachability for DAGs?
Justin Kilpatrick
CC BY-SA 3.0
2011-06-20T09:02:03.917Z
This doesn't seam much better than the naive dfs approach `(O(1),O(n^2))` or `(O(m),O(n+m))`.
Thomas Ahle
CC BY-SA 2.5
2011-02-27T01:24:54.473Z
2011-02-27T05:59:00.293Z
2011-02-27T05:59:00.293Z
virgi
<p>Given a directed acyclic graph, $G(V,E)$, is it possible to efficiently support the following operations?</p>

<ul>
<li>$isConnected(G,a,b)$: Determines if there is a path in $G$ from node $a$ to node $b$</li>
<li>$link(G,a,b)$: Adds an edge from $a$ to $b$ in the graph $G$</li>
<li>$unlink(G,a,b)$: Removes the edge from $a$ to $b$ in $G$</li>
<li>$add(G,a)$: Adds a vertex to G</li>
<li>$remove(G,a)$: Removes a vertex from G</li>
</ul>

<p>A few notes: </p>

<ul>
<li>If we disallowed $unlink$, it seems it would be easy to maintain the connectedness information, using a disjoint-set type data structure.</li>
<li>Obviously, $isConnected$ could be implemented using depth or breadth-first search, using the naive pointer-based representation of the graph. But this is inefficient.</li>
</ul>

<p>I'm hoping for amortized constant or logarithmic time for all three operations. Is this possible?</p>

CC BY-SA 2.5
2011-02-26T23:27:18.600Z
Related: The undirected graph version has been asked before.  [Is there an online-algorithm to keep track of components in a changing undirected graph?](http://cstheory.stackexchange.com/questions/2548/is-there-an-online-algorithm-to-keep-track-of-components-in-a-changing-undirected)
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-27T00:03:02.143Z
Could you explain how to solve the simpler case (without unlink) using a disjoint-set type data structure?
jbapple
CC BY-SA 2.5
2011-02-27T00:07:37.593Z
@Tsuyoshi - the links on that question look interesting, I am taking a look at them now.
Justin Kilpatrick
CC BY-SA 2.5
2011-02-27T00:15:12.850Z
(1) You are looking for a dynamic graph algorithm for directed reachability with the restriction that the graph is a DAG.  If I am not mistaken, dynamic directed reachability is much harder than the undirected counterpart, but here the DAG property might help.  (2) Does `remove` also remove the incident edges?  If so, requiring that operation to be O(log n) time might be too much to hope….
Tsuyoshi Ito
<ds.algorithms><graph-algorithms><directed-acyclic-graph><online-algorithms>
Does an algorithm exist to efficiently maintain connectedness information for a DAG in presence of inserts/deletes?
Justin Kilpatrick
# Does an algorithm exist to efficiently maintain connectedness information for a DAG in presence of inserts/deletes?

(Asked by: username_0 on 2011-02-26)

Given a directed acyclic graph, $G(V,E)$, is it possible to efficiently support the following operations?

* $isConnected(G,a,b)$: Determines if there is a path in $G$ from node $a$ to node $b$
* $link(G,a,b)$: Adds an edge from $a$ to $b$ in the graph $G$
* $unlink(G,a,b)$: Removes the edge from $a$ to $b$ in $G$
* $add(G,a)$: Adds a vertex to G
* $remove(G,a)$: Removes a vertex from G

A few notes:

* If we disallowed $unlink$, it seems it would be easy to maintain the connectedness information, using a disjoint-set type data structure.
* Obviously, $isConnected$ could be implemented using depth or breadth-first search, using the naive pointer-based representation of the graph. But this is inefficient.

I'm hoping for amortized constant or logarithmic time for all three operations. Is this possible?

**Tags:** ds.algorithms, graph-algorithms, directed-acyclic-graph, online-algorithms
> **Comments:**
> **username_1**: Related: The undirected graph version has been asked before.  [Is there an online-algorithm to keep track of components in a changing undirected graph?](http://cstheory.stackexchange.com/questions/2548/is-there-an-online-algorithm-to-keep-track-of-components-in-a-changing-undirected)  
> **username_2**: Could you explain how to solve the simpler case (without unlink) using a disjoint-set type data structure?  
> **username_0**: @Tsuyoshi - the links on that question look interesting, I am taking a look at them now.  
> **username_1**: (1) You are looking for a dynamic graph algorithm for directed reachability with the restriction that the graph is a DAG.  If I am not mistaken, dynamic directed reachability is much harder than the undirected counterpart, but here the DAG property might help.  (2) Does `remove` also remove the incident edges?  If so, requiring that operation to be O(log n) time might be too much to hope….  

---

## 2 answers

### Answer by username_4 on 2011-02-27. Score: 19 | Accepted answer

The problem you have described is fully dynamic DAG reachability (also referred to as fully dynamic transitive closure on DAGs).
It's called fully dynamic since people also study the versions where only deletions are possible (then it's called decremental reachability), and where only insertions are possible (called incremental reachability).

There are a few tradeoffs between the update time and the query time. Let $m$ be the number of edges and $n$ the number of vertices.
For DAGs, Demetrescu and Italiano (FOCS'00) gave a randomized data structure which supports updates (edge inserts or deletes) in O($n^{1.58}$) time and reachability queries in O($n^{0.58}$) time (node inserts/deletes are also supported, in O(1) time); this result was extended by Sankowski (FOCS'04) to work for general directed graphs. Also for DAGs, Roditty (SODA'03) showed that you can maintain the transitive closure matrix in total time O($mn+I·n^2+D$), where $I$ is the number of insertions, $D$ the number of deletions and of course the query time is O($1$).

For general directed graphs, the following (update, query) times are known:
(O($n^2$), O(1)) (Demetrescu and Italiano FOCS'00 (amortized), Sankowski FOCS'04 (worst case)), (O($m\sqrt{n}$), $O(\sqrt{n}$)) (Roditty, Zwick FOCS'02), (O($m+n\log n$), O($n$)) (Roditty, Zwick STOC'04), (O($n^{1.58}$),O($n^{0.58}$)) and (O($n^{1.495}$),O($n^{1.495}$)) by Sankowski (FOCS'04).

Obtaining a polylogarithmic query time, without increasing the update time too much is a major open problem, even for DAGs.

> **Comments:**
> **username_0**: Thank you for your answer. Although I have to say I'm disappointed at how poor those bounds are. :(  
> **username_0**: A related question: could you point me toward any references on the simpler problems, incremental reachability, and decremental reachability for DAGs?  
> **username_3**: This doesn't seam much better than the naive dfs approach `(O(1),O(n^2))` or `(O(m),O(n+m))`.  

---

### Answer by username_2 on 2011-02-27. Score: 4

I think the best results so far are discussed in ["Mantaining Dynamic Matrices for Fully Dynamic Transitive Closure"](http://arxiv.org/abs/cs.DS/0104001). That paper discusses a randomized algorithm with $O(n^{0.58})$ query time and an $O(n^{1.58})$ update time.

(This only covers the first version of your question, with `link` and `unlink` but without `add` and `remove`.)

> **Comments:**
> **username_3**: The bounds are build on Strassen's algorithm though, so the constant is huge.  

---

