17
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Related: The undirected graph version has been asked before. Is there an online-algorithm to keep track of components in a changing undirected graph? $\endgroup$ – Tsuyoshi Ito Feb 26 '11 at 23:27
  • 1
    $\begingroup$ Could you explain how to solve the simpler case (without unlink) using a disjoint-set type data structure? $\endgroup$ – jbapple Feb 27 '11 at 0:03
  • $\begingroup$ @Tsuyoshi - the links on that question look interesting, I am taking a look at them now. $\endgroup$ – Justin Kilpatrick Feb 27 '11 at 0:07
  • $\begingroup$ (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…. $\endgroup$ – Tsuyoshi Ito Feb 27 '11 at 0:15
19
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thank you for your answer. Although I have to say I'm disappointed at how poor those bounds are. :( $\endgroup$ – Justin Kilpatrick Feb 27 '11 at 5:43
  • 1
    $\begingroup$ A related question: could you point me toward any references on the simpler problems, incremental reachability, and decremental reachability for DAGs? $\endgroup$ – Justin Kilpatrick Feb 27 '11 at 5:59
  • $\begingroup$ This doesn't seam much better than the naive dfs approach (O(1),O(n^2)) or (O(m),O(n+m)). $\endgroup$ – Thomas Ahle Jun 20 '11 at 9:02
4
$\begingroup$

I think the best results so far are discussed in "Mantaining Dynamic Matrices for Fully Dynamic Transitive Closure". 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.)

$\endgroup$
  • $\begingroup$ The bounds are build on Strassen's algorithm though, so the constant is huge. $\endgroup$ – Thomas Ahle Jun 19 '11 at 22:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.