<p>You can check the <strong>Dynamic Transitive Closure Problem</strong> 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:</p>

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

<p>Some algorithms respond in <strong><em>$O(1)$</em></strong> time but need <strong>$O(n^2)$</strong> 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.</p>

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

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

<p>Take a look in the bibliography below:</p>

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

<p>Hope this helps!</p>

CC BY-SA 3.0
2016-06-23T13:06:53.647Z
Thank you! This lead me to the following paper: "A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time"
nemo
CC BY-SA 3.0
2016-06-24T09:14:15.153Z
No problem! Glad I could help!
Dimitris
CC BY-SA 3.0
2016-06-23T11:29:59.670Z
2016-06-23T11:29:59.670Z
Dimitris
<p>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$.</p>

<p>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.</p>

<p>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.</p>

<ds.algorithms><graph-theory><graph-algorithms>
Efficient update of reachable set of a node in a digraph
nemo
# Efficient update of reachable set of a node in a digraph

(Asked by: username_0 on 2016-06-23)

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.

**Tags:** ds.algorithms, graph-theory, graph-algorithms

---

## 1 answers

### Answer by username_1 on 2016-06-23. Score: 1 | Accepted answer

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!

> **Comments:**
> **username_0**: Thank you! This lead me to the following paper: "A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time"  
> **username_1**: No problem! Glad I could help!  

---

