Breaking an un-directed connected graph into two components

1
votes

Is there any algorithm to break a Connected Undirected Graph into exactly 2 connected components by deleting Minimum number of vertices.

Example 1: edge list [1-2, 2-3, 3-4], here we can delete vertex number 2 or vertex number 3 to decompose the graph into two connected component.

Example 2: edge list [1-2, 2-5, 2-3, 3-4], here we cannot delete vertex number 2 as it decomposes the graph into 3 connected components (which we don't want) but we can delete vertex number 3 to decompose the graph into two connected components.

1
c++algorithmdata-structurestreegraph-algorithm
Please clarify the following, Should the algorithm be able to recognize instances where a decomposition into exacly two connected components is impossible, like in the following edge list? [1-4, 2-4, 3-4] - Codor
Yes, or maybe just report how many connected components it is decomposing. - Mike Lewis

1 Answers

0
votes

You need to look for minimal vertex separator algorithm.