<p>PS: New to this SE, but old time SE/SO user.</p>
<p>Background study - I've gone through this, computer science and computational science SE and also various papers (skimmed) related to fully dynamic connectivity/bi-connectivity papers/algorithms and I still find my problem to be a bit different not solved/answered before.</p>
<p><strong>Problem Statement:</strong></p>
<p>I have an undirected graph of V vertices and E edges between those vertices. The core query I want to be able to answer is if this graph is disconnected. i.e. if there are more than one connected components in this graph.
This is easy to answer. I can do a basic floodfill and get an answer in O(V+E).</p>
<p>Now given a graph which is known to be connected, and you also have the articulation points calculated for that graph, I have to do N queries on this graph:</p>
<ul>
<li>Each query has a set of operation and then the core question.</li>
<li>This operation first removes X vertices from the graph and then adds Y nodes (these nodes maybe connected to one or more remaining vertex of the graph). It is assumed that the resulting graph is not the same graph as original. Also, V &gt; X &gt;= 0 and Y &gt;= 0 and X + Y &gt; 0</li>
<li>The operation is always performed on the original graph and are not incremental on top of the previous query.</li>
<li>The question remains the same. After doing the above operation, is the resultant graph disconnected?</li>
</ul>
<p>In a naive approach, I can disregard the original AP information and simply do N floodfills to figure out the result of the queries. That makes my time complexity to be O(N*(V+E))</p>
<p>But given that I have the AP info for the original graph and each query is run on some modification of the original graph, is there a more efficient way of doing this?</p>
<p>I am envisioning an algorithm/data structure/approach than can incrementally update the original AP info in logarithmic or poly-log time complexity and then answer the &quot;disconnected&quot; question in constant time (or along the way of that poly time complexity itself)</p>
<p>Thoughts? Is it even feasible? Any way to prove its feasible or not feasible?</p>

CC BY-SA 4.0
2024-11-06T20:35:13.253Z
There is a lot of literature on dynamic connectivity maintenance for edge removals/additions. One can do this poly-log update time. You can simulate vertex addition/deletion by removing edges incident to the vertices. You can search for dynamic data structure for connectivity.
Chandra Chekuri
CC BY-SA 4.0
2024-11-06T20:43:51.573Z
@ChandraChekuri None of the literature that I've come across solves for what i am asking in the question. If you've seen something similar, mind sharing the paper titles?
Most of the dynamic data structures worry about queries around biconnectivity or connectivity between two vertices. I am asking for something much more simpler and probably that can be done in much more efficient manner.
or if you know how I can reuse the literature and retrofit them in my use-case, please add an answer.
Optimizer
CC BY-SA 4.0
2024-11-06T21:51:53.967Z
See the paper below. It will give the MST cost when you add/delete edges. MST cost is infinity iff G is disconnected. @article{holm2001poly,
  title={Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity},
  author={Holm, Jacob and De Lichtenberg, Kristian and Thorup, Mikkel},
  journal={Journal of the ACM (JACM)},
  volume={48},
  number={4},
  pages={723--760},
  year={2001},
  publisher={ACM New York, NY, USA}
}
Chandra Chekuri
CC BY-SA 4.0
2024-11-07T04:06:52.157Z
@ChandraChekuri Thanks! I will take a look at this one.
Optimizer
CC BY-SA 4.0
2024-11-07T10:37:27.307Z
Do you have bounds on the size of X and Y? Because if not, deleting X and adding Y can create a completely new graph so there is no use in the information that the original graph was connected.
badboul
CC BY-SA 4.0
2024-11-07T10:57:23.727Z
Even if the size of X and Y is bounded by a constant, the algorithm of thorup et al mentioned above may not be helpful because there, the insertion/deletion of edges has a good amortized time which does not mean a good worst case time.
badboul
CC BY-SA 4.0
2024-11-07T12:07:43.887Z
@badboul In my practical use case, i am mostly dealing with single digit `X` and `Y`s while `V+E` can reach 100+ but the main reason why I want to optimize over `N` floodfills is because `N` can reach to billions.
Optimizer
CC BY-SA 4.0
2024-11-07T13:36:09.723Z
@ChandraChekuri looks like the paper you linked wont be helpful.. It suggests a theorem to do MST calculation in log^4 (N) but log^4 (N) > N for N < 5000 or so.. My graph would never have `V+E` > 5000 ..
Optimizer
CC BY-SA 4.0
2024-11-11T09:43:06.200Z
Since your graph, X, and Y are very small, it is very unlikely that a data structure with better worst case asymptotic runtime will be faster than breadth first search in practice. 
I have the following suggestion: Compute the k-connected components of your graph and the associated vertex cuts. Then, by counting how many vertices of each type are contained in X you may be able to determine that the graph remains connected. For example, if X contains only one vertex that is not an articulation point of your graph, then the graph remains connected after removing X.
badboul
CC BY-SA 4.0
2024-11-12T13:09:39.890Z
@badboul - yes, the case where X has just one node to remove is straight forward constant time operation, but as soon as there are more than 1 holes, it becomes tricky and it seems like relying on floodfill after apply X and Y operations is the only way to go.
Optimizer
CC BY-SA 4.0
2024-11-12T13:28:48.473Z
You can also list the 2-vertex cuts of the graph and if X contains two nodes that are not in this list than you know that X does not disconnect the graph (as described here: https://en.wikipedia.org/wiki/SPQR_tree). You can do the same for more than 2 vertices (as described here: https://en.wikipedia.org/wiki/K-vertex-connected_graph).
badboul
<graph-algorithms><time-complexity>
How to efficiently determine disconnects in a dynamic graph after performing N deletions and M additions
Optimizer
# How to efficiently determine disconnects in a dynamic graph after performing N deletions and M additions

(Asked by: username_0 on 2024-11-05)

PS: New to this SE, but old time SE/SO user.

Background study - I've gone through this, computer science and computational science SE and also various papers (skimmed) related to fully dynamic connectivity/bi-connectivity papers/algorithms and I still find my problem to be a bit different not solved/answered before.

**Problem Statement:**

I have an undirected graph of V vertices and E edges between those vertices. The core query I want to be able to answer is if this graph is disconnected. i.e. if there are more than one connected components in this graph.
This is easy to answer. I can do a basic floodfill and get an answer in O(V+E).

Now given a graph which is known to be connected, and you also have the articulation points calculated for that graph, I have to do N queries on this graph:

* Each query has a set of operation and then the core question.
* This operation first removes X vertices from the graph and then adds Y nodes (these nodes maybe connected to one or more remaining vertex of the graph). It is assumed that the resulting graph is not the same graph as original. Also, V > X >= 0 and Y >= 0 and X + Y > 0
* The operation is always performed on the original graph and are not incremental on top of the previous query.
* The question remains the same. After doing the above operation, is the resultant graph disconnected?

In a naive approach, I can disregard the original AP information and simply do N floodfills to figure out the result of the queries. That makes my time complexity to be O(N\*(V+E))

But given that I have the AP info for the original graph and each query is run on some modification of the original graph, is there a more efficient way of doing this?

I am envisioning an algorithm/data structure/approach than can incrementally update the original AP info in logarithmic or poly-log time complexity and then answer the "disconnected" question in constant time (or along the way of that poly time complexity itself)

Thoughts? Is it even feasible? Any way to prove its feasible or not feasible?

**Tags:** graph-algorithms, time-complexity

> **Comments:**
> **username_1**: There is a lot of literature on dynamic connectivity maintenance for edge removals/additions. One can do this poly-log update time. You can simulate vertex addition/deletion by removing edges incident to the vertices. You can search for dynamic data structure for connectivity.  
> **username_0**: @ChandraChekuri None of the literature that I've come across solves for what i am asking in the question. If you've seen something similar, mind sharing the paper titles? Most of the dynamic data structures worry about queries around biconnectivity or connectivity between two vertices. I am asking for something much more simpler and probably that can be done in much more efficient manner. or if you know how I can reuse the literature and retrofit them in my use-case, please add an answer.  
> **username_1**: See the paper below. It will give the MST cost when you add/delete edges. MST cost is infinity iff G is disconnected. @article{holm2001poly,   title={Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity},   author={Holm, Jacob and De Lichtenberg, Kristian and Thorup, Mikkel},   journal={Journal of the ACM (JACM)},   volume={48},   number={4},   pages={723--760},   year={2001},   publisher={ACM New York, NY, USA} }  
> **username_0**: @ChandraChekuri Thanks! I will take a look at this one.  
> **username_2**: Do you have bounds on the size of X and Y? Because if not, deleting X and adding Y can create a completely new graph so there is no use in the information that the original graph was connected.  
> **username_2**: Even if the size of X and Y is bounded by a constant, the algorithm of thorup et al mentioned above may not be helpful because there, the insertion/deletion of edges has a good amortized time which does not mean a good worst case time.  
> **username_0**: @username_2 In my practical use case, i am mostly dealing with single digit `X` and `Y`s while `V+E` can reach 100+ but the main reason why I want to optimize over `N` floodfills is because `N` can reach to billions.  
> **username_0**: @ChandraChekuri looks like the paper you linked wont be helpful.. It suggests a theorem to do MST calculation in log^4 (N) but log^4 (N) > N for N < 5000 or so.. My graph would never have `V+E` > 5000 ..  
> **username_2**: Since your graph, X, and Y are very small, it is very unlikely that a data structure with better worst case asymptotic runtime will be faster than breadth first search in practice.  I have the following suggestion: Compute the k-connected components of your graph and the associated vertex cuts. Then, by counting how many vertices of each type are contained in X you may be able to determine that the graph remains connected. For example, if X contains only one vertex that is not an articulation point of your graph, then the graph remains connected after removing X.  
> **username_0**: @username_2 - yes, the case where X has just one node to remove is straight forward constant time operation, but as soon as there are more than 1 holes, it becomes tricky and it seems like relying on floodfill after apply X and Y operations is the only way to go.  
> **username_2**: You can also list the 2-vertex cuts of the graph and if X contains two nodes that are not in this list than you know that X does not disconnect the graph (as described here: https://en.wikipedia.org/wiki/SPQR_tree). You can do the same for more than 2 vertices (as described here: https://en.wikipedia.org/wiki/K-vertex-connected_graph).  

---

## 0 answers

