I have an unweighted and undirected graph, and I want to divide this graph into two connected components by removing some vertices. The main objective is to minimize the number of vertices which must be deleted in order to partition the graph into two sub graphs.

How can I accomplish this ?

The first thing coming to my mind is Ford Fulkersonalgorithm, but I think it is not appropriate for this problem.

  • 3
    $\begingroup$ Google for minimum vertex cut. One of my top hits is e.g., this question. $\endgroup$ – Juho Apr 30 '18 at 20:33
  • $\begingroup$ What I cannot understand is why there is no reasonable solution for min vertex-cut. there is a specific algorithm ,which is Ford Fulkerson, for minimum ede cut. However, I cannot find senseful algorithm or solution for minimum vertex cut. $\endgroup$ – Goktug May 1 '18 at 10:58
  • $\begingroup$ Have you thought of a reduction that would allow you to use an algorithm for edge cuts to find vertex cuts? $\endgroup$ – Juho May 1 '18 at 11:22
  • $\begingroup$ Actually, I thought and I am thinking right now, but senseful reduction does not come to my mind. $\endgroup$ – Goktug May 2 '18 at 13:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.