More efficient vertex-labelling algorithm than BFS?

I am using the C++ boost library implementation of the push relabel algorithm to solve a max-flow problem. The output from that algorithm is a residual graph and in order to find the min-cut of my original graph, I need to find all of the vertices which are reachable from the source vertex in the residual graph.

I was planning to use BFS or DFS to traverse the residual graph, but I was wondering if there was any more efficient algorithms that anyone can suggest, as the size of my graphs are pretty large.

I plan on implementing my own, modified version of the push relabel algorithm eventually, and then I can probably label them as I go. But for now I would like to just run it with the boost library, so that I have something for comparison - but unfortunately that requires labelling the vertices separately.

Any suggestions would be greatly appreciated

• How big is your graph? Jun 21 '16 at 6:58
• potentially in the millions of vertices Jun 21 '16 at 6:59

For graphs that fit into main memory (or even in a largish L3 cache), you probably can't do much better than your library's traversal algorithm without significant effort.

But anyway, you're way into "try and measure" territory. Robert Sedgewick has a nice talk Putting the Science back into Computer Science, that explores flow problems as an example. He uses Ford-Fulkerson, not push-relabel.

It's quite clear that you can't be better in terms of asymptotic bounds, at least not without further knowledge of the graph.

There may be some margin of improvement in the implementation, though, in particular if the graph is huge: parallelisation, considering memory hierarchy, and so on.

Also, note that there may be ways in the max-flow algorithm to get around computing everything anew in every step. You may want to check out Dinic's algorithm.

The running time of BFS and DFS are asymptotically optimal (they can find all reachable vertices in linear time, i.e., linear in the number of reachable vertices), so you can't hope to do better by more than a constant factor.

Constant factors tend to depend heavily on platform-specific details (e.g., cache effects, the memory hierarchy) more than on algorithmics, so if you're looking for constant-factor speedups, that's probably off-topic here and more a matter of optimizing your code.

• Okay, thanks for that. So between DFS and BFS, if the graph is very large with a lot of edges, I would probably be better off using DFS, as it has O(bd) space complexity as opposed to O(b^d), but both have the same time complexity? Jun 21 '16 at 6:58
• @guskenny83, what's $b$ and what's $d$? Space complexity is not easy to compare. You might want to ask a new question about space complexity, after doing some research into it.
– D.W.
Jun 21 '16 at 7:05