Benchmarking Complexity of Dinic's With Scaling

Revision en7, by Chilli, 2019-03-19 04:49:23

In various places(1, 2, ), people have talked about "Dinic's With Scaling" having $O(VElog(U))$ complexity, where U is the max edge capacity. However, in just as many places, people have cast doubt about this complexity or worried that this algorithm ends up being slower in practice(12.

I had the same doubts. In fact, a couple months ago I benchmarked Dinic's with scaling on some hard test cases and thought that Dinic's with/without scaling performed similarly.

As it turns out, I benchmarked it again yesterday and found that Dinic's with scaling definitely has significantly better asymptotic complexity (by a factor of V).

## Synthetic Benchmarking

I used the hard test case generator at 2 posted by ko_osaga here. The one posted at 1 creates a graph with only V edges and moreover, doesn't work for me... Notably, given a V, it generates a graph with V nodes and $O(V^2)$ edges.

The code I used was my own Dinic's implementation (originally from emaxx) found here. Notably, the SCALING variable toggles between Dinic's with scaling and without. It's a small change, as you can see.

I ran the two code across a variety of input sizes, averaging across 10 runs, then taking the log of input size and times, plotting them in a where blue is the runtime of Dinic's without scaling and orange is the runtime of Dinic's with scaling. Since the important thing to look at is the slope of the line, I normalized the lines to start at the same point.

Fitting a linear regression to the points, we see that the slope of Dinic's without scaling is 3.204, while the slope of Dinic's with scaling is 1.93, which correspond to complexities of $O(V^3)$ and $O(V^2)$ respectively.

In terms of actual runtime, here are some numbers on specific sizes.

## Benchmarking on Problems

There are 3 flow problems, I benchmarked on — SPOJ FASTFLOW, (VNSPOJ FASTFLOW)[https://vn.spoj.com/problems/FFLOW/), and a Chinese LOJ Flow Problem (it's intended to solve this problem with Highest Label Preflow Push, which has $O(V^2\sqrt{E})$ complexity).

Also, to vouch for the superiority of my solution, here's some benchmarks with other implementations :^) Mine (to enable scaling change the SCALING boolean), Emaxxs dinic, LOJ fastest (HLPP, the fastest submission on the Chinese flow problem).

SPOJ (V<=5000, E<=3e4)
Mine: 0.04
Emaxx Dinic: 0.11
Mine w/ scaling: 0.27
LOJ fastest: 0.10

VNSPOJ (V<=5000, E<=3e4, harder test cases):
Mine: TLE
Emaxx dinic: TLE
Mine w/ scaling: 0.00
LOJ fastest: 0.00

LOJ (V<=1200, E<=120000):
Mine: 56 points
Mine w/ scaling: 88 points
Emaxx dinic: 44 points
LOJ fastest: AC, 1176 ms total, #1 on leaderboard

Synthetic Test(N=2000, E=4e6):
Mine: 66.56
Emaxx dinic: 247.40
Mine w/ scaling: 0.14 LOJ fastest: 0.10

#### History

Revisions

Rev. Lang. By When Δ Comment
en13 Chilli 2019-03-19 10:44:20 2 Tiny change: 'astest: 0.10 \n\n\nV' -> 'astest: 0.00 \n\n\nV'
en12 Chilli 2019-03-19 10:13:29 109
en11 Chilli 2019-03-19 06:34:52 2 Tiny change: 'haracters:\nMine: 11' -> 'haracters: \nMine: 11'
en10 Chilli 2019-03-19 06:34:35 5
en9 Chilli 2019-03-19 06:33:16 784 (published)
en8 Chilli 2019-03-19 05:16:53 101
en7 Chilli 2019-03-19 04:49:23 108
en6 Chilli 2019-03-19 04:30:32 4 Tiny change: ' fastest: \n\n\n' -> ' fastest: 0.10\n\n\n'
en5 Chilli 2019-03-19 04:17:31 540
en4 Chilli 2019-03-19 03:39:48 334
en3 Chilli 2019-03-18 22:14:30 1042 Tiny change: 'them in a chart.\n' -> 'them in a ![chart](https://i.imgur.com/gKqkpgd.jpg)\n\n'
en2 Chilli 2019-03-18 05:07:24 1400
en1 Chilli 2019-03-18 00:08:21 291 Initial revision (saved to drafts)