3
$\begingroup$

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?

Improve this question
$\endgroup$
11
  • $\begingroup$ 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. $\endgroup$
    – Chandra Chekuri
    Commented Nov 6 at 20:35
  • $\begingroup$ @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. $\endgroup$
    – Optimizer
    Commented Nov 6 at 20:43
  • 1
    $\begingroup$ 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} } $\endgroup$
    – Chandra Chekuri
    Commented Nov 6 at 21:51
  • 1
    $\begingroup$ 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. $\endgroup$
    – badboul
    Commented Nov 11 at 9:43
  • 1
    $\begingroup$ 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). $\endgroup$
    – badboul
    Commented Nov 12 at 13:28

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.