# Network flow on multigraph easier than I thought?

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): 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): 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) 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

• 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. Oct 2, 2022 at 22:05
• 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. Oct 3, 2022 at 12:42
• 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. Oct 3, 2022 at 12:55