Divide vertices of undirected graph to two groups by minimum number of edges

Question

Assume I have an undirected, connected graph G(V,E).
I want to find an algorithm that divides the vertices in V to two groups by the goal: minimum number of edges connecting between the two groups.
For example, in the following graph:

  A 
 / \
B - C
| / |
D   E

The algorithm will return the groups: {E}, {A,B,C,D} since the minimum number is one edge connecting the groups. All other options are greater then one.
The runtime complexity should be less then $O(|V|^6)$.

I think it can be solved using Ford-Fulkerson, min cut-max flow theorem, but I havn't found the solution.

Answer 1

Yes, you can do this with Ford-Fulkerson. You can use FF to find a maximum flow, and a corresponding minimum cut, between any given pair of vertices. You want the minimum cut without this restriction, but that just means you need the smallest minimum cut you can get for any pair of vertices, so you just need to run FF $O(n^2)$ times. (In fact you can fix one of the vertices so $O(n)$ times is enough.)