Trying to find an input that actually runs in O(E*f) for Ford Fulkerson when using DFS

#	User	Rating
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	djm03178	152

Context: Find the maximum flow through a directed graph from s to t. Capacities are all integers.

If I'm not mistaken, Edmonds-Karp runs in O(VE²); and if we don't use a BFS but a DFS instead, it runs in O(E*f) where f is the maximum flow (https://en.wikipedia.org/wiki/Maximum_flow_problem) (proofs: https://enos.itcollege.ee/~japoia/algorithms/GT/Introduction_to_algorithms-3rd%20Edition.pdf chapter 26).

I was a bit surprised that Edmonds-Karp wouldn't pass (but I guess it makes sense looking at the constraints) on a cses problem ( https://cses.fi/problemset/task/1694 ). What really surprised me is that the O(E*f) solution passed (https://cses.fi/paste/aba73738dacf15c9ac0337/ even though the capacities can go up to 10^9 so the max flow can definitely go up to 10^9). I'm now trying to hack my own DFS solution, so I tried to hardcore brute force it by generating billions of inputs and seeing if my DFS would time out on one of them: https://pastebin.com/ijUZDn3G. But that ran so fast (within a minute..) without finding any bad cases...

The worst-case example on wikipedia for that O(E*f) (https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm) doesn't work for a fixed adjacency list. It just shows that if a bad actor could choose what order DFS goes through the graph, then the algorithm could become crazily slow.

I heard there is this test case generator to hack those O(E*f) solutions but I'll be honest, I don't speak Japanese and I'm not advanced enough to figure out what's happening: https://web.archive.org/web/20211009144446/https://min-25.hatenablog.com/entry/2018/03/19/235802

TL;DR: this code passes https://cses.fi/paste/aba73738dacf15c9ac0337/ even though it's O(E*f) and the capacities can go up to 10^9; please hack me.

(EDIT: my comment in the code saying "DFS to find shortest s-t path" is wrong, it's a remnant comment from when I was coding BFS)

Comments (3)

Write comment?

lotusblume

104 minutes ago, # |

Here is a graph where augmenting paths with DFS requires exponential running time:

Spoiler

This graph is actually test 20 of the CSES problem. There are two reasons why it doesn't work on your algorithm:

The graph is very sensitive to the order of the vertices in the adjacency lists. Test 20 only works, if all edges (and reverse edges!!!) are added into the adjacency lists in the order of the input. You add the reverse edges later in lines 41 and 42. This messes up the intended order.
Your algorithm isn't a DFS. When you search through the neighbours of vertex u and find a new vertex v you continue looking for other neighbours of vertex u. However a DFS would immediately stop searching for neighbours of u and instead look for neighbours of v.

If you add 3 lines to "fix" these things: https://cses.fi/paste/a31c0c721baec2b1ac0707/, then you actually get time limit exceeded on test 20.

Of course it is stupid to change your algorithm so that it performs worse. But the above graph can be slightly modified such that your implementation also has an exponential running time. The following code generates an instance where your code needed more than 2 minutes on my PC to solve it.

Generator Code

#include <algorithm>
#include <cassert>
#include <iostream>
#include <tuple>
#include <vector>

const int INF = 1000000000;

struct Edge {
	int from, to, cap;
	Edge(int u, int v, int w) : from(u), to(v), cap(w) {}
	bool operator<(const Edge& o) {
		return std::tie(from, to) < std::tie(o.from, o.to);
	}
};

int main() {
	// Your algorithm will need approximately 2^k augmenting paths
	int k = 20;

	std::vector<Edge> edges;

	int cur1 = 4 * k + 1;
	int cur2 = 6 * k + 3;

	int s = cur2--;
	int t = cur2--;

	edges.emplace_back(s, t, 2);

	for (int i = 1, w = 2; i <= k; ++i, w *= 2) {
		assert(w <= INF / 2);
		int s2 = cur2--;
		int t2 = cur2--;
		edges.emplace_back(s2, cur1, w);
		edges.emplace_back(cur1--, s, w);
		edges.emplace_back(s2, cur1, w);
		edges.emplace_back(cur1--, t, w);
		edges.emplace_back(s, cur1, w);
		edges.emplace_back(cur1--, t2, w);
		edges.emplace_back(t, cur1, w);
		edges.emplace_back(cur1--, t2, w);
		s = s2;
		t = t2;
	}

	int s2 = 1;
	int t2 = 6 * k + 4;

	edges.emplace_back(s2, s, INF);
	edges.emplace_back(t, t2, INF);

	int cur_sz = (int) edges.size();

	for (int i = 0; i < cur_sz; ++i) {
		edges.emplace_back(edges[i].to, edges[i].from, 1);
	}

	std::sort(edges.begin(), edges.end());

	std::cout << 6 * k + 4 << ' ' << (int) edges.size() << '\n';

	for (const Edge& e : edges) {
		std::cout << e.from << ' ' << e.to << ' ' << e.cap << '\n';
	}

	return 0;
}

→ Reply

JasonMendoza2008

46 minutes ago, # ^ |

← Rev. 3 →

Thank you so much. Small question, you say my algorithm isn't a DFS (because I add every neighbour to the stack and then and only then I pop). Isn't that the only way to write an iterative DFS? Can we really write an iterative DFS that doesn't iterate through all neighbours before popping from the stack? EDIT i’m stupid you had changed/fixed it your example, thanks for taking the time!!

wery0

19 minutes ago, # ^ |

Can you already hack my SPFA algorithm please? :D

https://codeforces.net/blog/entry/124509?#comment-1106057

JasonMendoza2008's blog