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.
