0
$\begingroup$

I encountered many articles on max-flow problem that do not go beyond simple graphs in which two nodes are either connected with a single directed edge OR two nodes are connected with a single undirected edge, therefore making the capacity symmetric.

When two nodes are connected with more than one edge, they use "tricks" where they add a vertex for each (anti-)parallel edge in order to bring the edge count back to 1.

I felt like it should be easier to solve than this and decided to take the following convoluted example graph (http://graphonline.ru/en/?graph=TPcWPNOZEBxlsGOS):

original graph

This is the original graph. We can simplify the graph as follows:

  1. remove self-loops, as they do not affect the flow
  2. merge parallel edges by summing up their capacities.
  3. whenever a (u, v) edge exists, make sure (v, u) edge exists already, otherwise add (v, u) edge with weight 0

We obtain the following simplified graph (http://graphonline.ru/en/?graph=tAZGhegGqBFtrqcT):

simplified graph

This graph can be treated as the Residual graph in the Edmonds-Karp algorithm. Whenever we push X flow from (u, v), the residual capacity of (u, v) decreases by X, and the residual capacity of (v, u) increases by X. This allows us to "cancel" that flow later if an augmenting path goes through those edges. In no case do we send more flow than allowed by the original edge capacities.

When I run the algorithm on this simplified graph, I obtain the following flow graph. (http://graphonline.ru/en/?graph=EkLlCnaCWfXVDyTb)

flow graph

It shows that the maximum flow of the original graph is 13, which seems reasonable.

My gut tells me that if it actually was this simple, it would have been already discovered and would have been taught this way. Am I missing a critical piece of information here? Please let me know.

PS: Here are the directed edges list as https://graphonline.ru/ asks:

original graph:

0-(3)>1
0-(6)>1
0-(5)>2
1-(3)>0
1-(10)>1
1-(7)>2
1-(6)>3
2-(2)>0
2-(10)>1
2-(7)>4
3-(1)>1
3-(5)>1
3-(11)>4
3-(12)>4
3-(10)>5
4-(30)>3
4-(2)>5
4-(3)>5
5-(7)>3
5-(1)>4
5-(2)>5

simplified graph:

0-(9)>1
0-(5)>2
1-(3)>0
1-(7)>2
1-(6)>3
2-(2)>0
2-(10)>1
2-(7)>4
3-(6)>1
3-(23)>4
3-(10)>5
4-(0)->2
4-(30)>3
4-(5)>5
5-(7)>3
5-(1)>4

flow graph

0-(8)>1
0-(5)>2
1-(2)>2
1-(6)>3
2-(7)>4
3-(8)>5
4-(2)>3
4-(5)>5
Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I didn't check your graphs but the approach works in the sense that it preserves the value of the maximum flow. To get a flow for the original graph you just need to distribute the flow on each edge $(u,v)$ of the simplified graph back to the parallel edges from $u$ to $v$ in the original graph. This can be done arbitrarily as long as the capacities are not exceeded. $\endgroup$
    – Steven
    Oct 2, 2022 at 22:05
  • $\begingroup$ Yes exactly I thought of that as well, since the edges do not have any "identity" so to speak. I wonder why they make it seem so complicated in those books/articles. It seems that simply merging edge capacities is much cleaner/easier than adding vertex for every (anti-)parallel edge. $\endgroup$
    – Mehdi Saffar
    Oct 3, 2022 at 12:42
  • 1
    $\begingroup$ I don't have an answer to that, but splitting an edge doesn't sound more complicate than summing the edge weights to me. Also, the approach breaks down if you add costs, so perhaps the presentation of max-flows it is used as a stepping stone towards min-cost (max-)flows. $\endgroup$
    – Steven
    Oct 3, 2022 at 12:55

0

Reset to default

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.

Browse other questions tagged or ask your own question.