How to check if given set of nodes is the vertex cut set of the graph?

1
votes

I am looking for efficient algorithm to discover whether removing a set of nodes in graph would split graph into multiple components.

Formally, given undirected graph G = (V,E) and nonempty set od vertices W ⊆ V, return true iff W is vertex cut set. There are no edge weights in graph.

What occurs to my mind until now is using disjoint set:

  • The disjoint set is initialized with all neigbors of nodes in W where every set contains one such neighbor.
  • During breadth-first traversal of all nodes of V \ W, exactly one of following cases holds for every newly explored node X:
    • X is already in same set as its predecessor
    • X is absent in disjoint set ⇒ is added into same set as its predecessor (both cases mean the connected component is being further explored)
    • X is in different set ⇒ merge disjoint sets (two components so far appeared as disconnected but turned out to be connected)
  • Whenever the disjoint set contains only single set (even before traversal is finished), result is false.
  • If the disjoint set contains 2 or more sets when traversal is finished, result is true.

Time complexity is O(|V|+|E|) (assuming time complexity of disjoint set is O(1) instead of more precise inverse Ackermann function).

Do you know better solution (or see any flaw in proposed one)?

Note: Since it occurs very often in Google search results, I would like to explicitly state I'm not looking for algorithm to find so-far-unknown vertex cut set, let alone optimal. The vertex set is given, the task is just to say yes or no.

Note 2: Also, I don't search for edge cut set validation (I'm aware of Find cut set in a graph but can't think up similar solution for vertices).

Thanks!

UPDATE: I figured out that in case of true result I will also need data of nodes in disconnected components in hierarchical structure depending on distance from removed nodes. Hence the choice of BFS. I apologize for post-edit.

The practical case behind is an outage in telecommunication network. When some node breaks so the whole network get disconnected, one component (containing the node with connectivity to higher level network) is still ok, every other components need to be reported.

2
algorithmgraphgraph-theorygraph-traversal

2 Answers

2
votes

Have a unordered_set<int> r to store the set of vertices you want to remove.

Run a DFS normally, but only go to adjacents who are not in r. Always you visit an unvisited node, add 1 to the number of nodes visited.

If in the end, the number of visited nodes is smaller than |V| - r, this set divides the graph.

With this approach, you don't need to make changes in the graph, just ignore nodes that are in r, which you can check in O(1) using an unordered_set<int>.

The complexity is the same than a normal DFS.

1
votes

Can’t you get O(|V|) complexity by performing a depth first search on the graph? Eliminate the set W from V and perform DFS. Record the number of nodes processed and stop when you cannot reach any more nodes. If the number of nodes processed is less than |V| - |W|, then W is a cut set.