17

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?

Justin Kilpatrick
  • 173
  • 5

2 Answers2

19

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.

virgi
  • 2,489
  • 19
  • 25
4

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.)

jbapple
  • 11,184
  • 2
  • 29
  • 50