2

I know that in undirected connected graph articulation point is a vertex after removing which graph becomes disconnected. For Java code I followed this link http://algs4.cs.princeton.edu/41undirected/Biconnected.java.html.

Now suppose we have above graph- enter image description here

In above graph there are no articulation points because graph does not become disconnected by removing any single vertex. But we can make graph disconnected by removing more than 1 vertex, for example if we remove 4,6 vertices graph becomes disconnected.

How to find set of vertices such that after removing those vertices graph becomes disconnected. Lets say that there is limit of vertices that can be removed and it is 3. Meaning we cannot remove more than 3 vertices at a time to make graph disconnected.

Approach I am thinking-

Step 1 - Run algorithm to find single articulation point.

Step 2 - If after step 1 there is no articualtion point we remove a vertex from graph and run articulation point algorithm, we do this for all vertices in graph. Using this we can find 2 vertices (1st is vertex that was removed before running algo and 2nd vertex is found after running algo) whose removal will make graph disconnected and program will stop because we have found set of vertices.

Step 3 - If we are not able to find set of vertices in step 2, we remove 2 vertices from graph and run articulation point algorithm. We run this algorithm after removing each pair of graph vertices. Using it we can find set of 3 vertices removing which graph will be disconnected. If still graph is not disconnected we dont run program any further because our limit of vertices that can be removed is 3.

I think there is better approach for this.

How to find minimum set of vertices after removing which graph becomes disconnected.

What can be the better approach to find set of vertices removing which graph becomes disconnected.

anujprashar
  • 6,263
  • 7
  • 52
  • 86

2 Answers2

3

See http://www.cs.colorado.edu/~hal/Papers/expandersC.ps.gz for the best algorithm that I know of for calculating minimum vertex cuts.

btilly
  • 43,296
  • 3
  • 59
  • 88
2

For any vertex with degree (i.e., neighbour count) d, removing all d of its neighbours will disconnect the graph (unless those are the only other vertices in the graph). So that right away gives you an upper bound on the number of vertices you will need to delete, as well as the actual vertices you could delete to achieve that bound: Just look for a vertex of minimum degree, and delete all of its neighbours.

In your example graph, you know this is the optimal solution, since there are vertices with degree 2, and you have already ruled out solutions of size 1 because you have found that the graph is biconnected (i.e., contains no articulation point). In general however, it may be possible to do better than this upper bound: For example, consider a graph consisting of 2 copies of a clique on k vertices, plus 2 additional edges (u1, v1) and (u2, v2), with u1 and u2 from the first clique and v1 and v2 from the second. This can be disconnected by deleting just u1 and u2 (or just v1 and v2), even though the minimum degree, k, can be made arbitrarily large.

j_random_hacker
  • 50,331
  • 10
  • 105
  • 169
  • Follow this links, might help you in your quest (http://stackoverflow.com/questions/15873153/explanation-of-algorithm-for-finding-articulation-points-or-cut-vertices-of-a-gr) and (http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/) – letsBeePolite May 13 '15 at 12:53
  • 2
    @skn: I'm not sure how those help -- they just describe how to find all articulation points, which the OP is already able to do. – j_random_hacker May 13 '15 at 12:56