Network Stream: Add a New Edge

Question

Recently, in one of the compilations, I was asked to develop an algorithm that for a network having V vertices and E edges, if by adding an edge (it capacity should be 1) results in increase the maximum flow. , that is, we must develop such an algorithm to find such edges.

The algorithm should be faster than O(|E|* h(|V||E|)) , where h(|V||E|) is the time taken to calculate the maximum flow.

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

Answer 1

(Fixed version of what Philip said.) Calculate the maximum flow. Remove an untethered, directional graph consisting of arcs with positive residual capacity. Adding a specific arc increases the maximum flow if and only if there are paths from source to tail and from head to receiver, that is, introducing an arc creates an expansion path.

In your example, {s->a, a->b, a->c, a->d, b->t, c->t, d->t} maximum flow 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 each inverse arc {a->s, b->a, c->a, d->a, t->b, t->c, t->d} . The vertices reached from s are {s} , and the vertices reached from t are {t} , so the only arc that can increase the maximum flow is s->t .

Answer 2

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

• find the minimum cut with the total weight of the edge X using, for example, 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 the nodes that belong to separate sections of the section (S, S') , i.e. adds the edge (u,v) , where u is in S and v is in S' .
• repeat until there are no more cuts with a total weight of edge X

Answer 3

I think the solution could be:

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

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

Answer 4

Another solution might be the following:

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

Step 2. Find the minimum section containing the maximum number of vertices (let's call it the vertices Vmax).

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

Why does it work? (I) Adding a new uv-edge is good if it is contained in each minimal section (more precisely: if it connects the various components of the minimal section) and (II) the "group" of minimal sections is close to the union and intersection.

Complexity:

For Step1,2, I found the following nice algorithm: How to find the minimum cut in the graph using the maximum flow algorithm? . This can be used to find the minimum cut with minimum and maximum vertices. This is apparently done at h (| E || V |) + O (| V | ^ 3), where O (| V | ^ 3) comes from the BFS when you check if the BFS is complete (i.e. e. residual neighboring exists).

For step 3, we have O (| Vmin | * | V \ Vmax |) such that O (| V | ^ 2).

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

Please note that this is just a quick sketch :)