2

In the recent time in one of the compition I have been asked to design an algorithm that, for a network having V vertices and E edges, if by adding an edge (it's capacity should be 1) results in increase the maximum flow. that is we have to design such an algoritm to find such edges.

Algorithm should be faster then O(|E|* h(|V||E|)) where h(|V||E|) is time taken in computing maximum flow.

Thanks in advance. Let me know if it is unclear.

4 Answers4

1

(Corrected version of what Philip said.) Compute a maximum flow. Extract an uncapacitated, directed graph consisting of the arcs with positive residual capacity. Adding a particular arc increases the maximum flow if and only if there are paths from the source to the tail and from the head to the sink, i.e., the introduction of the arc creates an augmenting path.

In your example {s->a, a->b, a->c, a->d, b->t, c->t, d->t}, the maximum flow is s-3>a, a-1>b, a-1>c, a-1>d, b-1>t, c-1>t, d-1>t, and the residual graph has every backward arc {a->s, b->a, c->a, d->a, t->b, t->c, t->d}. The vertices reachable from s are {s} and the vertices reachable from t are {t}, so the only single arc that could increase the max flow is s->t.

fight the powah
  • 11
  • 1
0

According to the Max-Flow-Min-Cut-Theorem [1], the maximum flow in a network is equal to the sum of all edge weights in a minimum cut. Hence a solution might look like this:

  • find a minimum cut with total edge weight X by using e.g. the Edmonds-Karp-Algorithm, a specialization of the Ford-Fulkerson-Algorithm. According to [1], this is in O(h|V||E|).
  • add an edge that connects nodes that belong to distinct partitions of the cut (S, S'), i.e. add an edge (u,v) where u is in S and v is in S'.
  • repeat until there are no more cuts with total edge weight X.
Philip
  • 5,795
  • 3
  • 33
  • 68
  • 2
    I don't think that this would always work. Consider the case: `{s->a, a->b, a->c, a->d, b->t, c->t, d->t}`with the edge `s->a` with weight 3 and all other edges with weight 1. Then, we have {s,a}, {b,c,d,t} in S and S' respectively. Now adding an edge from `a->t` still wouldn't increase the max flow. –  Nov 05 '11 at 11:59
  • @Kevin: Your cut has weight 3, but there is a cut of weight 1: S={s}, S'={a,b,c,d,t}. Still, not all of the edges in S x S' increase the max flow, though. – Erik P. Nov 05 '11 at 15:15
  • @ErikP. The weight of the edge `s->a` is 3 as mentioned in my first comment. So the cut that you consider will also be weight 3. Therefore, my cut is also valid and then the algorithm fails in that case. Am I correct? –  Nov 05 '11 at 15:33
  • Sorry - I somehow missed the "with weight 3" part. You're correct. – Erik P. Nov 07 '11 at 21:26
0

I think the solution can be:

  1. First run maximum flow algorithm. Now, we have the residual graph G.
  2. Then we find all edge (u, v) such that in the residual graph G, we can find a path from s to u and path from v to t.

The complexity in the worst case is O(|V|^2(|V|+|E|) + h(|V||E|)).

gunhnart
  • 1
  • 1
  • I don't understand your complexity calculation. Shouldn't it be `O(|V|^3 + h(|E||V|)` as we just try to find paths from s to u and v to t in `O(|V|)` time for every possible edge, i.e. `O(|V|^2)` –  Nov 06 '11 at 10:02
  • I'm sorry. I made it wrong. The complexity of the first step (find max flow) is h(|E||V|). For the second step: To find all edges, we have to check all pair of vertex (u,v); for each pair (u,v), we have to run BFS (or DFS) in the residual graph to find the path from s to u and v to t. The complexity of BFS is O(|V|+|E|). Thus, the complexity of the second step is O(|V|^2(|V|+|E|)). – gunhnart Nov 07 '11 at 00:56
0

Another solution could be the following:

Step 1. Find a minimum cut containing the minimum number of vertices (call its vertices Vmin).

Step 2. Find a minimum cut containing the maximum number of vertices (call its vertices Vmax).

Step3. Find all edges that link Vmin and V\Vmax but not part of E.

Why does this work? (I) Adding a new uv edge is good iff it is contained in every minimal cut (to be precise: if it links the different components of the minimum cut) and (II) the 'group' of minimum cuts is close against union and intersection.

Complexity:

For Step1,2 I've found the following nice algorythm: How can I find the minimum cut on a graph using a maximum flow algorithm?. This could be applied to find the minimum cut with minimum and maximum vertices. This seems to run in h(|E||V|) + O(|V|^3), where O(|V|^3) comes from the BFS when you check whether BFS is ended (ie. no more new residual adjacent exists).

For Step3 whe have O(|Vmin| * |V\Vmax|) that is O(|V|^2).

Hence Step1,2,3 = h(|E||V|) + O(|V|^3)

Note that this is just a quick sketch:)

Community
  • 1
  • 1
Gyula
  • 54
  • 2