1

I'm working with an undirected graph where I need to frequently add and remove edges. I also need to efficiently determine the number of connected components after each operation.

For adding edges, I've found that using a Disjoint Set Union data structure provides a very efficient way to merge components and track the number of sets using the union operation.

However, removing an edge with a standard DSU seems to be less efficient. If an edge removal disconnects a component, the DSU doesn't inherently provide a way to easily split the sets. The typical approach seems to involve re-initializing the whole Disjoint Set Union, which is slow for a large number of edges.

Just to be clear I'll provide an example

Consider a graph with vertices V = {1, 2, 3, 4, 5} and initial edges E = {(1, 2), (2, 3), (4, 5)}. The connected components are {1, 2, 3} and {4, 5}.

Adding an edge (3, 4) results in new edges E' = {(1, 2), (2, 3), (4, 5), (3, 4)} and a single connected component {1, 2, 3, 4, 5}. Disjoint Set Union efficiently handles this.

Now, removing edge (2, 3) leaves edges E'' = {(1, 2), (4, 5), (3, 4)} and new connected components {1, 2} and {3, 4, 5}. The challenge is that using only a basic DSU I need to go though the whole graph to determine the connected components.

Improve this question

2 Answers 2

Reset to default
1

If you would like to efficiently dissect components upon removing edges (when necessary), just to decide whether the component falls into two parts, you'd have to search for connections not just locally, but across the component (to see if it is still one connected component), which would hint that a 1D data structure isn't sufficient to quickly gather this information, rather using a graph data structure or equivalent representations (e.g. adjacency matrix).

I can suggest a direction you can take that may help:

Adjacency matrix, ordered rows and columns: If you take the adjacency matrix and order the rows and columns such that nodes of a component continuously make up a section (i.e., sort the rows and columns e.g. by index of the component), then the matrix will consist of blocks (along the diagonal) representing the components, with 0 entries anywhere outside these blocks. There cannot be any connections between the components, which is why there are only 0 entries outside the blocks.
Two diagonal blocks in an adjacency matrix, representing two disjoint components

You may make use of this in multiple ways, I've seen sorting based on BFS be useful. Probably there is a fast solution in this direction.

For example, after removing an edge, you may run BFS on only the nodes in the component that had an edge removed; and see if there are two blocks along the diagonal that have only 0 entries "across them". Here, you can apply just a simple sum operation to check if the component split to two (the sum of cells "across" the two blocks is zero).
It may speed up the block searching that the edge removed has to have one node in one block and the other node in the other block, if there are 2 disjoint blocks after removing the edge.
You may also make use of conditions when it's easy to tell that the component will not split into two, and skip the calculations.

I'm thinking of some other approach where you store some other information between pairs of nodes (2D matrix) that can be used analogous to a look-up table to check if two nodes become disconnected if the edge between them was removed, updating this information quickly using paths, but so far I didn't come up with anything interesting.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

This is pretty much what I ended up doing in the end. Current approach to edge removal involves running a BFS on the connected components affected by each removal. The problem with this method is its efficiency: unlike adding edges, which Union-Find handles with near-constant time complexity, edge removal can be as slow as O(N+E) (N is nodes and E is edges) in the worst case when the entire graph is connected. This is simply too slow for my application.
0

Use Tarjan's Algorithm ( https://en.wikipedia.org/wiki/Biconnected_component ) to keep track of the cut vertices in each component. If the removed edge does NOT involve one of the cut vertices, then the number components cannot change, but you will have to recalculate the cut vertices in the component containing the removed edge. If it does, then you will have to recalculate your components and cut vertices from scratch.

Improve this answer

1 Comment

Tarjan’s algorithm can indeed be efficient when removing a single node or edge, because you can check if it affects cut vertices or bridges. I can see how this would be useful when removing nodes or edges that don’t really affect anything, since I wouldn’t need to recalculate the components in those cases. But what if I have a sequence of node or edge removals? Wouldn’t I still need to go through the entire graph after each change? It seems that Tarjan’s results wouldn’t stay valid after each update, so I’d have to rerun it repeatedly.

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.