<p>Most research regarding time complexity of dynamic reachability looks at an index structure which is updated and then queried.  It would be useful to know why you want an immediate query?  The link studies this idea from a descriptive complexity approach although time complexities aren't given for the queries.</p>
<p><a href="https://arxiv.org/pdf/1512.05511.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1512.05511.pdf</a></p>

CC BY-SA 4.0
2021-01-08T17:35:18.847Z
I'm interested in such a case because incremental transitive closure with such behavior is a part of a context-free path querying algorithm that we are working on. Briefly: we have an iterative algorithm that supports transitive closure of directed graph $G$, at each iteration adds new edges in the $G$, and uses newly reachable pairs to calculate edges that should be added at the next iteration. So, we want to use existing results to provide accurate time complexity analysis.
gsv
CC BY-SA 4.0
2021-01-08T15:55:50.663Z
2021-01-08T15:55:50.663Z
Ryan Dorsey
<p>The typical definition of dynamic transitive closure (or reachability) uses two types of queries: the first one is an update (edge deletion/insertion) and the second one is a reachability query. Thus, most works on time complexity provide separated estimations on update operation and reachability query evaluation. But what about the case when one wants to get new reachability facts immediately on the update? So, we have only update queries, and as a result of each edge insertion we want to get all new reachable pairs (for edge deletion --- all pairs that became unreachable, for example). Are there any results on the theoretical time complexity of such a case?</p>

CC BY-SA 4.0
2023-01-30T09:49:36.710Z
Interesting -- how would you measure the complexity in this case? Given that a single update can make a quadratic number of pairs change (e.g., you have n vertices connected to n vertices via a single edge), you can't hope to produce all changed pairs in less than quadratic time in the worst case. I'm guessing you would count the complexity as a function of the number of changes to produce?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-01-30T09:51:02.913Z
Also, it's not clear to me why there wouldn't be reductions between the standard setting and yours. If we have a data structure supporting only your mode of operation, you can possibly use it to emulate the standard way to do queries, by encoding them as updates: have a super-source r and super-sink vertex s, then whenever you want to query if x can reach y, then connect the r to x, connect y to s, and test if the pair (r, s) is now produced?
Antoine Amarilli 'a3nm'
<graph-algorithms><dynamic-algorithms><transitive-closure>
Dynamic transitive closure with immediate new reachability facts
gsv
# Dynamic transitive closure with immediate new reachability facts

(Asked by: username_0 on 2021-01-08)

The typical definition of dynamic transitive closure (or reachability) uses two types of queries: the first one is an update (edge deletion/insertion) and the second one is a reachability query. Thus, most works on time complexity provide separated estimations on update operation and reachability query evaluation. But what about the case when one wants to get new reachability facts immediately on the update? So, we have only update queries, and as a result of each edge insertion we want to get all new reachable pairs (for edge deletion --- all pairs that became unreachable, for example). Are there any results on the theoretical time complexity of such a case?

**Tags:** graph-algorithms, dynamic-algorithms, transitive-closure
> **Comments:**
> **username_1**: Interesting -- how would you measure the complexity in this case? Given that a single update can make a quadratic number of pairs change (e.g., you have n vertices connected to n vertices via a single edge), you can't hope to produce all changed pairs in less than quadratic time in the worst case. I'm guessing you would count the complexity as a function of the number of changes to produce?  
> **username_1**: Also, it's not clear to me why there wouldn't be reductions between the standard setting and yours. If we have a data structure supporting only your mode of operation, you can possibly use it to emulate the standard way to do queries, by encoding them as updates: have a super-source r and super-sink vertex s, then whenever you want to query if x can reach y, then connect the r to x, connect y to s, and test if the pair (r, s) is now produced?  

---

## 1 answers

### Answer by username_2 on 2021-01-08. Score: 0

Most research regarding time complexity of dynamic reachability looks at an index structure which is updated and then queried. It would be useful to know why you want an immediate query? The link studies this idea from a descriptive complexity approach although time complexities aren't given for the queries.

<https://arxiv.org/pdf/1512.05511.pdf>

> **Comments:**
> **username_0**: I'm interested in such a case because incremental transitive closure with such behavior is a part of a context-free path querying algorithm that we are working on. Briefly: we have an iterative algorithm that supports transitive closure of directed graph $G$, at each iteration adds new edges in the $G$, and uses newly reachable pairs to calculate edges that should be added at the next iteration. So, we want to use existing results to provide accurate time complexity analysis.  

---

