Benchmarking Complexity of Dinic's With Scaling

Revision en2, by Chilli, 2019-03-18 05:07:24

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...

The code I used was my own Dinic's implementation (originally from emaxx but with pretty heavy modifications) 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 chart.


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