CODEWITHSUNDEEP
algorithmgraph-algorithmgraph-theorydepth-first-search
Gaston
Gaston

Reputation: 994

DFS count isolated nodes for articulation points

I have a graph and a starting node. I want to find how many nodes become isolated when I remove each node in the graph, for all nodes, using DFS.

For example, if I start on a fixed node 1, and remove node 2, how many isolated nodes I will have? and if I remove node 3?

I know I can just do DFS for all nodes(removing a different node each time), but doing so I will have to navigate the graph one time for each node, I want to solve it with just one run.

I have been told it has O(|V|*||A|), being |V|=number of edges, and |A|= number of nodes.

I've been playing with prenum and postnums, but with no success.

Upvotes: 0

Views: 661

Answers (1)

Lucas Sampaio
Lucas Sampaio

Reputation: 316

Let N be the number of vertices and M be the number of edges. If you just want a O(NM) solution as you stated, you don't need to go any further than running a DFS for each vertex.

The complexity for each DFS is O(N+M) so the total complexity will be of O(N(N+M)) = O(N²+NM). Usually we have more edges than vertices, so NM grows much faster than N² and we can say that the complexity is of O(NM). Keep in mind, though, that if you physically delete the current vertex at each step your implementation will have a much worse complexity, because physically deleting a vertex means removing entries from a lot of adjacency lists, which is costly no matter how you represent the graph. There is an implementation trick to speed up the process: instead of physically deleting the current vertex before each DFS, just mark the vertex as deleted, and when you are going through the adjacency lists during the DFS just ignore the marked vertex.

However, i feel that you can solve this problem in O(N+M) using Tarjan's algorithm for finding articulation points. This algorithm will find every vertex that, when removed from the graph, splits the graph in more than one connected component (these vertices are called articulation points). It's easy to see that there won't be isolated vertices if you remove a vertex that is not an articulation point. However, if you remove an articulation point, you will split the graph in two parts G and G', where G is the connected component of the starting vertex, and G' is the rest of the graph. All vertices from G' are isolated because you can't reach them if you run a DFS from the starting vertex. I think that you can find the size of G' for each vertex deletion efficiently, maybe you can even do this while running Tarjan's. If i find a solution i can edit this answer later.

EDIT: i managed to solve the problem in O(N+M). I will give some hints so you can find the answer by yourself:

  1. Every undirected graph can be decomposed in (not disjoint) sets of biconnected components: each biconnected component is a subset of the vertices of the graph where every vertex in this subset will remain connected even if you remove any vertex of the graph

  2. Tarjan's O(N+M) algorithm to find bridges and articulation points can be altered in order to find the biconnected components, finding which vertices belong to each biconnected component, or which biconnected components contain each vertex

  3. If you remove any vertex that is not an articulation point, answer for this vertex is obviously N-1

  4. If you remove an articulation point, every vertex in the same biconnected component of the starting vertex will still be acessible, but you don't know about the other biconnected components. Don't worry, there is a way to find this efficiently

  5. You can compress every graph G in a graph B of its biconnected components. The compression algorithm is simple: every biconnected component becomes a vertex in B, and you link biconnected components that share some articulation point. We can prove that the resulting graph B is a tree. You must use this tree somehow in order to solve the problem presented in step 4

Good luck!

Upvotes: 2

Related Questions