1
$\begingroup$

Given a graph $G(V, E)$ with capacities on the edges such that all edges have a capacity of $\sqrt2$ apart from one edge with a capacity of 2. need to find max flow efficiently.

I can run Dinic on this graph or FordFulkerson but I know it can be more time-efficient.

What I have tried -

transform all edges capacity to be 1, then find max flow using Dinic algorithm on 0-1 network that is more efficient than a general network. then If the edge that had a capacity of 2 isn't saturated it won't be saturated on the original graph so we can just find the min-cut and multiply the number of edges that cross the min-cut by $\sqrt 2$ and that's the max flow. but if it's saturated I'm stuck.

Improve this question
$\endgroup$
2
  • $\begingroup$ I'm not familiar with this topic, but could you map $\langle \sqrt{2}, 2 \rangle \to \langle 2, 3 \rangle$ and then use the Goldberg-Rao algorithm here for a time complexity of $O( \min( V^{2/3}, E^{1/2} ) E \log (V^2 / E) )$? $\endgroup$
    – D. G.
    Mar 4, 2020 at 14:23
  • 1
    $\begingroup$ @D.G. If you map $\sqrt{2},2 \to 2,3$, you have no guarantee that the max flow with these new capacities will be related in some simple manner to the max flow with the original capacities. (If you multiply all capacities by some constant then you can divide the result by the same constant afterwards to get an answer, but this doesn't seem all that useful here, although it might be a good idea to start by scaling $\sqrt{2},2 \to 1,\sqrt{2}$, I don't know) $\endgroup$
    – Tassle
    Mar 4, 2020 at 15:55

2 Answers 2

Reset to default
1
$\begingroup$

First, you can divide all capacities by $\sqrt{2}$ so that all capacities are now $1$ except for a single edge $e'$ which has capacity $\sqrt{2}$.

Call this instance $G$. Create $G_1$ which is a copy of $G$ where the capacity of $e'$ has been replaced with $1$, and find the max flow of this graph, with a value $F_1$.

Now, consider $G_2$ which is also a copy of $G$ where the capacity of $e'$ has been replaced with $2$ and has a max flow of $F_2$.

If $F_2 > F_1$, this means that starting from the flow assignment of maximum flow in $G_1$ there is an augmenting path in $G_2$ along which you can push $1$ additional unit of flow. This augmenting path necessarily corresponds to an augmenting path in $G$ where you can push $\sqrt{2}-1$ additional units of flow. Thus, the max flow for $G$ is $F=F_1 + \sqrt{2}-1$.

If $F_2 = F_1$, this means that starting from the flow assignment of maximum flow in $G_1$ there is no augmenting path in $G_2$ along which you can push any amount of flow. This also means that this holds for $F$, as the capacity increase of $e'$ between $F_1$ and $F$ is lower than between $F_1$ and $F_2$. Thus, the max flow for $G$ is $F=F_1$.

(You just need a single search of augmenting path to determine if $F_2 > F_1$ or $F_2 = F_1$ once you have computed the flow for $F_1$)

Then, to get the answer to your original problem, just scale the flow back by multiplying $F$ by $\sqrt{2}$.

Improve this answer
$\endgroup$
1
$\begingroup$

Hint:

In the optimal solution, either the edge of weight 2 is saturated or it isn't. Handle those two cases separately.

Hint #2:

If I told you the edge of weight 2 it is saturated in the optimal solution, could you find that solution? What if I told you it isn't saturated?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.