Many people think they know how to solve the min-cost-max-flow problem, but most of them only know how to solve it with pseudo-polynomial time algorithm (although it usually runs very fast). And in this blog, min_25 provided a counter case generator, most people's MCMF algorithm runs in $$$O(2^{\frac n 2}n^2\log n)$$$ on it.
the counter case
42 421
1 2 1 0
1 3 3 0
1 4 5 0
1 5 10 0
1 6 20 0
1 7 40 0
1 8 80 0
1 9 160 0
1 10 320 0
1 11 640 0
1 12 1280 0
1 13 2560 0
1 14 5120 0
1 15 10240 0
1 16 20480 0
1 17 40960 0
1 18 81920 0
1 19 163840 0
1 20 327680 0
1 21 655360 0
2 22 5242880 0
2 23 5242880 1
2 24 5242880 3
2 25 5242880 7
2 26 5242880 15
2 27 5242880 31
2 28 5242880 63
2 29 5242880 127
2 30 5242880 255
2 31 5242880 511
2 32 5242880 1023
2 33 5242880 2047
2 34 5242880 4095
2 35 5242880 8191
2 36 5242880 16383
2 37 5242880 32767
2 38 5242880 65535
2 39 5242880 131071
2 40 5242880 262143
2 41 5242880 524287
3 22 5242880 1
3 24 5242880 3
3 25 5242880 7
3 26 5242880 15
3 27 5242880 31
3 28 5242880 63
3 29 5242880 127
3 30 5242880 255
3 31 5242880 511
3 32 5242880 1023
3 33 5242880 2047
3 34 5242880 4095
3 35 5242880 8191
3 36 5242880 16383
3 37 5242880 32767
3 38 5242880 65535
3 39 5242880 131071
3 40 5242880 262143
3 41 5242880 524287
4 22 5242880 3
4 23 5242880 3
4 25 5242880 7
4 26 5242880 15
4 27 5242880 31
4 28 5242880 63
4 29 5242880 127
4 30 5242880 255
4 31 5242880 511
4 32 5242880 1023
4 33 5242880 2047
4 34 5242880 4095
4 35 5242880 8191
4 36 5242880 16383
4 37 5242880 32767
4 38 5242880 65535
4 39 5242880 131071
4 40 5242880 262143
4 41 5242880 524287
5 22 5242880 7
5 23 5242880 7
5 24 5242880 7
5 26 5242880 15
5 27 5242880 31
5 28 5242880 63
5 29 5242880 127
5 30 5242880 255
5 31 5242880 511
5 32 5242880 1023
5 33 5242880 2047
5 34 5242880 4095
5 35 5242880 8191
5 36 5242880 16383
5 37 5242880 32767
5 38 5242880 65535
5 39 5242880 131071
5 40 5242880 262143
5 41 5242880 524287
6 22 5242880 15
6 23 5242880 15
6 24 5242880 15
6 25 5242880 15
6 27 5242880 31
6 28 5242880 63
6 29 5242880 127
6 30 5242880 255
6 31 5242880 511
6 32 5242880 1023
6 33 5242880 2047
6 34 5242880 4095
6 35 5242880 8191
6 36 5242880 16383
6 37 5242880 32767
6 38 5242880 65535
6 39 5242880 131071
6 40 5242880 262143
6 41 5242880 524287
7 22 5242880 31
7 23 5242880 31
7 24 5242880 31
7 25 5242880 31
7 26 5242880 31
7 28 5242880 63
7 29 5242880 127
7 30 5242880 255
7 31 5242880 511
7 32 5242880 1023
7 33 5242880 2047
7 34 5242880 4095
7 35 5242880 8191
7 36 5242880 16383
7 37 5242880 32767
7 38 5242880 65535
7 39 5242880 131071
7 40 5242880 262143
7 41 5242880 524287
8 22 5242880 63
8 23 5242880 63
8 24 5242880 63
8 25 5242880 63
8 26 5242880 63
8 27 5242880 63
8 29 5242880 127
8 30 5242880 255
8 31 5242880 511
8 32 5242880 1023
8 33 5242880 2047
8 34 5242880 4095
8 35 5242880 8191
8 36 5242880 16383
8 37 5242880 32767
8 38 5242880 65535
8 39 5242880 131071
8 40 5242880 262143
8 41 5242880 524287
9 22 5242880 127
9 23 5242880 127
9 24 5242880 127
9 25 5242880 127
9 26 5242880 127
9 27 5242880 127
9 28 5242880 127
9 30 5242880 255
9 31 5242880 511
9 32 5242880 1023
9 33 5242880 2047
9 34 5242880 4095
9 35 5242880 8191
9 36 5242880 16383
9 37 5242880 32767
9 38 5242880 65535
9 39 5242880 131071
9 40 5242880 262143
9 41 5242880 524287
10 22 5242880 255
10 23 5242880 255
10 24 5242880 255
10 25 5242880 255
10 26 5242880 255
10 27 5242880 255
10 28 5242880 255
10 29 5242880 255
10 31 5242880 511
10 32 5242880 1023
10 33 5242880 2047
10 34 5242880 4095
10 35 5242880 8191
10 36 5242880 16383
10 37 5242880 32767
10 38 5242880 65535
10 39 5242880 131071
10 40 5242880 262143
10 41 5242880 524287
11 22 5242880 511
11 23 5242880 511
11 24 5242880 511
11 25 5242880 511
11 26 5242880 511
11 27 5242880 511
11 28 5242880 511
11 29 5242880 511
11 30 5242880 511
11 32 5242880 1023
11 33 5242880 2047
11 34 5242880 4095
11 35 5242880 8191
11 36 5242880 16383
11 37 5242880 32767
11 38 5242880 65535
11 39 5242880 131071
11 40 5242880 262143
11 41 5242880 524287
12 22 5242880 1023
12 23 5242880 1023
12 24 5242880 1023
12 25 5242880 1023
12 26 5242880 1023
12 27 5242880 1023
12 28 5242880 1023
12 29 5242880 1023
12 30 5242880 1023
12 31 5242880 1023
12 33 5242880 2047
12 34 5242880 4095
12 35 5242880 8191
12 36 5242880 16383
12 37 5242880 32767
12 38 5242880 65535
12 39 5242880 131071
12 40 5242880 262143
12 41 5242880 524287
13 22 5242880 2047
13 23 5242880 2047
13 24 5242880 2047
13 25 5242880 2047
13 26 5242880 2047
13 27 5242880 2047
13 28 5242880 2047
13 29 5242880 2047
13 30 5242880 2047
13 31 5242880 2047
13 32 5242880 2047
13 34 5242880 4095
13 35 5242880 8191
13 36 5242880 16383
13 37 5242880 32767
13 38 5242880 65535
13 39 5242880 131071
13 40 5242880 262143
13 41 5242880 524287
14 22 5242880 4095
14 23 5242880 4095
14 24 5242880 4095
14 25 5242880 4095
14 26 5242880 4095
14 27 5242880 4095
14 28 5242880 4095
14 29 5242880 4095
14 30 5242880 4095
14 31 5242880 4095
14 32 5242880 4095
14 33 5242880 4095
14 35 5242880 8191
14 36 5242880 16383
14 37 5242880 32767
14 38 5242880 65535
14 39 5242880 131071
14 40 5242880 262143
14 41 5242880 524287
15 22 5242880 8191
15 23 5242880 8191
15 24 5242880 8191
15 25 5242880 8191
15 26 5242880 8191
15 27 5242880 8191
15 28 5242880 8191
15 29 5242880 8191
15 30 5242880 8191
15 31 5242880 8191
15 32 5242880 8191
15 33 5242880 8191
15 34 5242880 8191
15 36 5242880 16383
15 37 5242880 32767
15 38 5242880 65535
15 39 5242880 131071
15 40 5242880 262143
15 41 5242880 524287
16 22 5242880 16383
16 23 5242880 16383
16 24 5242880 16383
16 25 5242880 16383
16 26 5242880 16383
16 27 5242880 16383
16 28 5242880 16383
16 29 5242880 16383
16 30 5242880 16383
16 31 5242880 16383
16 32 5242880 16383
16 33 5242880 16383
16 34 5242880 16383
16 35 5242880 16383
16 37 5242880 32767
16 38 5242880 65535
16 39 5242880 131071
16 40 5242880 262143
16 41 5242880 524287
17 22 5242880 32767
17 23 5242880 32767
17 24 5242880 32767
17 25 5242880 32767
17 26 5242880 32767
17 27 5242880 32767
17 28 5242880 32767
17 29 5242880 32767
17 30 5242880 32767
17 31 5242880 32767
17 32 5242880 32767
17 33 5242880 32767
17 34 5242880 32767
17 35 5242880 32767
17 36 5242880 32767
17 38 5242880 65535
17 39 5242880 131071
17 40 5242880 262143
17 41 5242880 524287
18 22 5242880 65535
18 23 5242880 65535
18 24 5242880 65535
18 25 5242880 65535
18 26 5242880 65535
18 27 5242880 65535
18 28 5242880 65535
18 29 5242880 65535
18 30 5242880 65535
18 31 5242880 65535
18 32 5242880 65535
18 33 5242880 65535
18 34 5242880 65535
18 35 5242880 65535
18 36 5242880 65535
18 37 5242880 65535
18 39 5242880 131071
18 40 5242880 262143
18 41 5242880 524287
19 22 5242880 131071
19 23 5242880 131071
19 24 5242880 131071
19 25 5242880 131071
19 26 5242880 131071
19 27 5242880 131071
19 28 5242880 131071
19 29 5242880 131071
19 30 5242880 131071
19 31 5242880 131071
19 32 5242880 131071
19 33 5242880 131071
19 34 5242880 131071
19 35 5242880 131071
19 36 5242880 131071
19 37 5242880 131071
19 38 5242880 131071
19 40 5242880 262143
19 41 5242880 524287
20 22 5242880 262143
20 23 5242880 262143
20 24 5242880 262143
20 25 5242880 262143
20 26 5242880 262143
20 27 5242880 262143
20 28 5242880 262143
20 29 5242880 262143
20 30 5242880 262143
20 31 5242880 262143
20 32 5242880 262143
20 33 5242880 262143
20 34 5242880 262143
20 35 5242880 262143
20 36 5242880 262143
20 37 5242880 262143
20 38 5242880 262143
20 39 5242880 262143
20 41 5242880 524287
21 22 5242880 524287
21 23 5242880 524287
21 24 5242880 524287
21 25 5242880 524287
21 26 5242880 524287
21 27 5242880 524287
21 28 5242880 524287
21 29 5242880 524287
21 30 5242880 524287
21 31 5242880 524287
21 32 5242880 524287
21 33 5242880 524287
21 34 5242880 524287
21 35 5242880 524287
21 36 5242880 524287
21 37 5242880 524287
21 38 5242880 524287
21 39 5242880 524287
21 40 5242880 524287
22 42 2 0
23 42 2 0
24 42 5 0
25 42 10 0
26 42 20 0
27 42 40 0
28 42 80 0
29 42 160 0
30 42 320 0
31 42 640 0
32 42 1280 0
33 42 2560 0
34 42 5120 0
35 42 10240 0
36 42 20480 0
37 42 40960 0
38 42 81920 0
39 42 163840 0
40 42 327680 0
41 42 655360 0
I tried to find learning materials of polynomial minimum cost flow algorithms, but I can only find papers like A Faster Strongly Polynomial Minimum Cost Flow Algorithm and Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, and I can't understand them very well.
Are there any other learning materials besides the papers? Thanks in advance.
UPD. I've learned an algorithm with time complexity of $$$O(m^2\log U\log m)$$$ ($$$U$$$ refers to the maximum capacity), for Chinese and those who want to see my code, I wrote a blog; for those who want English learning materials, the one mentioned in Laakeri's comment is good.
cp-algorithms has an article for Dinic's.
It's an algorithm for maximum flow without cost.
I am a bit confused here. According to CP-Algorithms, if we use the Edmonds-Karp algorithm with Bellman-Ford in order to find the lowest-cost path between the source and the sink vertices, then the complexity is $$$O(n^2m^2)$$$, where $$$n$$$ is the number of vertices and $$$m$$$ is the number of edges. Where are you getting this $$$O(2^{n/2}n^2\log n)$$$ complexity from?
Have you tested it on the counter case I mentioned in this blog?
Unfortunately, my main language is English, so I did not understand the blog post. What is the format of the test case? Does every line represent an edge?
The format for each line is $$$(from, to, capacity, cost)$$$.
The runtime of that algorithm is $$$O(f \cdot n m)$$$ where $$$f$$$ is the number of augmenting paths. The article incorrectly claims that $$$f \in O(n m)$$$. This is wrong, as we're considering shortest paths with edge weights. For unweighted graphs, any path has length at most $$$n$$$ (and you have at most $$$m$$$ augmenting paths of every length, hence the $$$n m$$$ bound on $$$f$$$ in the unweighted case), but this is obviously not true for weighted graphs (where the length of a path is the sum of its weights).
Oh, that is very interesting. Just curious, but is there any way to get the complexity of $$$f$$$ in terms of $$$n$$$ and $$$m$$$? Also, where does the $$$O(2^{n/2}n^2\log n)$$$ complexity come from?
You can read this paper. It's related with $$$n$$$ because it's a specific construction.
While I've only seen in described in papers, I've found the successive approximation algorithm by Goldberg and Tarjan a natural generalization of the push relabel algorithm (it also uses a height function and push and relabel operations). The paper Solving Minimum-Cost Flow Problems by Successive Approximation on it should be easier to read than the two you linked, especially if you're familiar with push-relabel. The algorithm runs in $$$O(n^3 \log(n C))$$$ where $$$C$$$ is the maximum edge cost (so it's polynomial in the input size but not strongly polynomial) and it is fast in practice.
IIRC you can do capacity scaling with the successive shortest path algorithm (linked on CP-Algorithms above) to get something like $$$O(m^2 \log n \log U)$$$ where $$$U$$$ is the largest edge capacity. This would also be polynomial but not strongly polynomial. This algorithms might be easier to understand as you can first study both components (the capacity scaling and the successive shortest paths) separately.
Thank you very much! I watched a video and I think now I understand the basic idea of capacity scaling.
Won't scaling for min cost max flow possibly create negative cycles?
Sure, so I guess it's not that simple. At the start of each scaling phase, let's add edges that now get a positive capacity one by one and at each point check whether it is included in a negative cycle and update the potentials so that we have no negative edges. (And only look for augmenting paths after adding all edges). Note that the newly added edge is the only edge with negative reduced weight, so this check boils down to running Dijkstra's algorithm to find a path from one endpoint of the edge to the other one (similarly to how we find the augmenting paths).
Equivalently, we could saturate all newly added edges which have negative reduced weight. This creates some excesses and deficits, which we resolve by finding augmenting paths. As we saturated all negative edges, we only deal with edges of non-negative costs, so we can keep using Dijkstra's. (This involves at most $$$m$$$ augmenting paths, so the runtime remains the same.)
https://web.stanford.edu/class/cs361b/files/cs361b-notes.pdf — this material has an in-depth explanation about a capacity scaling mincost flow algorithm that has $$$O(m^2 \log U)$$$ time complexity. I have implemented the algorithm in here.
Could you please explain the "fixPotentials" function (especially how does it avoid the overflow, and the range of potentials after fixing)? Or is it in the notes (the pdf)? I have just read the first 19 pages.
I tried to implement the capacity scaling algorithm mentioned in Theorem 3.1 but failed, because there are many places which need "sufficiently large number"s, and the relationship of these "sufficiently large number"s are really confusing, overflow may also happen. I read your implementation and found the "fixPotentials" function which may help.
You are right. The issue with the algorithm is that there is no proof about how the values of the potential function behave, and in naive implementations they might grow exponentially during the algorithm.
The fixPotentials function is intended to fix this issue. I wrote it 3 years ago, so I don't remember details anymore, but my documentation (which is written in finnish) says that it works in $$$O(m \log n)$$$ time, and after running it, the maximum absolute value of a potential will be $$$nC$$$, where $$$C$$$ is the maximum absolute value of a cost in the input.
Here is my old description of the fixPotentials function: Select a vertex $$$v$$$ whose potential has not been fixed yet. Then compute the shortest paths (with the old potential function) from $$$v$$$ using only the vertices that are not fixed yet. For all vertices $$$u$$$ reached from $$$v$$$, set the new potential $$$p(u)$$$ as the length of the shortest path from $$$v$$$ + the greatest fixed potential before this stage. Repeat this process until all vertices have been fixed.
I have just implemented it, and I found another way to "fix potentials" (in fact it's mentioned in the notes) — add an extra node s to the residual graph, add zero-cost edges from s to each node in the residual graph, for each node v, assign p(v) = dist(s, v).
And I also found negative reduced costs in Dijkstra in your implementation.
My implementation is here.
Thx. I implemented your approach and got even faster solution, thanks to using indexed heap instead of priority queue
Could you please share your implementation?
rust version