# Efficient update of reachable set of a node in a digraph

Given a digraph $G = (V, E)$ and a set of vertices $S$, which does not change over the whole process, the goal is to compute the set of vertices, $R_{reach}$, reachable from $S$ and the set of nodes , $R_{ret}$, from which I can return to $S$.

The issue I have now, is that I need to add and remove edges. I can keep track of the changes in the graph. Note that these changes to the graph only happen locally, i.e. within a given range/distance around a vertex I know.

I have successfully been localizing the update of $R_{reach}$ and $R_{ret}$ for the edges I add to the graph. However, when I remove an edge from the graph one issue arises, that this edge might cut off a subgraph in term of reachability/returnability. I am not sure if it is possible to keep the update of $R_{reach}$ and $R_{ret}$ still local around the known vertex and the given update distance or if it is faster to simply recompute $R_{reach}$ and $R_{ret}$ for the whole graph again using BFS.

You can check the Dynamic Transitive Closure Problem of a Digraph. The transitive closure (or reachability) problem in a digraph $G=(V,E)$ consists in finding whether there is a directed path between any two vertices in $G=(V,E)$. The general idea is to maintain some kind of structure in order to quickly respond to queries of the form:

is there a path connecting u and v? Now add/delete an edge $e \in E$: is there a path connecting u and v?

Some algorithms respond in $O(1)$ time but need $O(n^2)$ space. Some respond yes/no and some also give you an actual path though I do not remember the exact complexity to get the path.

For your case you have to check all nodes of $S$ against all other nodes $V-S$.

The easiest way to do it is to run BFS every time for every node in $S$. It depends on the application.

Take a look in the bibliography below:

• D. Yellin, Speeding up dynamic transitive closure, Acta Informatica 30 (1993), pp.369-384.
• [I86] G. Italiano, Amortized Efficiency of a Path Retrieval Data Structure, Theoretical Computer Science, 48 (1986), pp. 273-281.
• [I88] G. Italiano, Finding Paths and Deleting Edges in Directed Acyclic Graphs, Information Processing Letters, 28 (1988), pp. 5-11.

Hope this helps!

• Thank you! This lead me to the following paper: "A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time" – nemo Jun 23 '16 at 13:06
• No problem! Glad I could help! – Dimitris Jun 24 '16 at 9:14