Timeline for How to efficiently determine disconnects in a dynamic graph after performing N deletions and M additions
Current License: CC BY-SA 4.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Nov 16 at 11:01 | history | bounty ended | CommunityBot | ||
| S Nov 16 at 11:01 | history | notice removed | CommunityBot | ||
| Nov 12 at 13:28 | comment | added | badboul | 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: en.wikipedia.org/wiki/SPQR_tree). You can do the same for more than 2 vertices (as described here: en.wikipedia.org/wiki/K-vertex-connected_graph). | |
| Nov 12 at 13:09 | comment | added | Optimizer | @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. | |
| Nov 11 at 9:43 | comment | added | badboul | 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. | |
| S Nov 8 at 9:56 | history | bounty started | Optimizer | ||
| S Nov 8 at 9:56 | history | notice added | Optimizer | Draw attention | |
| Nov 7 at 13:36 | comment | added | Optimizer |
@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 ..
|
|
| Nov 7 at 12:07 | comment | added | Optimizer |
@badboul In my practical use case, i am mostly dealing with single digit X and Ys 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.
|
|
| Nov 7 at 10:57 | comment | added | badboul | 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. | |
| Nov 7 at 10:37 | comment | added | badboul | 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. | |
| Nov 7 at 4:06 | comment | added | Optimizer | @ChandraChekuri Thanks! I will take a look at this one. | |
| Nov 6 at 21:51 | comment | added | Chandra Chekuri | 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} } | |
| Nov 6 at 20:43 | comment | added | Optimizer | @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. | |
| Nov 6 at 20:35 | comment | added | Chandra Chekuri | 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. | |
| Nov 6 at 20:01 | history | edited | Optimizer |
added a tag
|
|
| S Nov 5 at 19:35 | review | First questions | |||
| Nov 6 at 10:09 | |||||
| S Nov 5 at 19:35 | history | asked | Optimizer | CC BY-SA 4.0 |