Finding minimum cut edges in a graph

Question

Given a random undirected graph, I must find 'bottleneck edges' (edit: minimum cut edges) to get from one vertex to another.

What I call 'bottleneck edges' (edit: minimum cut edges) -- suppose I have the following undirected graph:

    A
  / | \
 B--C--D
 |     |
 E--F--G
  \ | /
    H

To get from A to H independently of the chosen path edges BE and DG must always be traversed, therefore making a 'bottleneck' (edit: minimum cut).

Is there a polynomial time algorithm for this?

Solution 1

Sounds like you need minimum cut, the minimal set of edges removing which will separate your graph into two pieces.

http://en.wikipedia.org/wiki/Minimum_cut

Solution 2

What you are looking for is a cut. Given a graph, a cut is a set of edges that partitions the vertices into two disjoint subsets.

Assuming you are trying to get the smallest cut possible, this is the classic min-cut problem. Here is a pseudo code version of the Ford-fulkerson algorithm, reworked for your case (undirected, unweighted graphs). I'm pretty sure it should work, but I am not sure I'm being the most efficient / idiomatic here.

reorganize your graph into a directed graph,
  with two directed edges (u->v, v->u) for each original edge (u-v)

while there is a path P from A to H:
  (hint: use breadth first search to find paths - long story here)
  //augment the path P:
  for each edge (u->v) in P:
    remove (u->v) from the graph and add (v->u) to it
    (if v->u isn't there already)

Label all vertices as reacheable or not reacheable from A.

The bottleneck edges is the set of edges
  that connect a reacheable and a unreacheable vertex

---

For example, in your case BFS would give us the path A-B-E-H. After removing these edges, we would still be able to find the path A-D-G-H. After these edges are removed, the graph is partitioned into the reacheable vertices {A,B,C,D} and the unreacheable {E,F,G,H}. The edges that have a vertex from each (B-E and D-G) set are the bottleneck edges.

Comments

[Admin]

This might well be it. And use Max flow = min-cut :-)

[Rohan Desai]

I forgot if using BFS would allow us to straight up remove the edges (in this unweighted, undirected), instead of doing all the directed edge stuff. Does anyone remember this?

[Noros]

Thanks, yes, minimum cut it is! :)