Multiterminal planar flow

The main point of this post is to talk about two recent arXiv preprints on maximum flow algorithms, "Multiple-Source Multiple-Sink Maximum Flow in Planar Graphs" (arXiv:1012.4767) by Yahav Nussbaum, and "Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in \( O(n^{3/2}\log n) \) Time" (arXiv:1012.5870) by Shay Mozes. However, first I'd like to set the stage by apologizing for some sloppy scholarship in the literature survey component of one of my own papers.

In my recent ISAAC paper "Flows in One-Crossing-Minor-Free Graphs" with Erin Chambers, we wrote "Due to known separator theorems for minor-closed families, an algorithm of Johnson and Venkatesan can be applied to find flows in any minor-closed family in time \( O(n^{3/2}\log n) \)". But this appears to be overstated at best, and more likely just wrong. Johnson and Venkatesan's paper is about flows in planar networks, and they use both simple-cycle separators (having the property that contracting one side of the separator preserves planarity) and the duality between cuts and paths in the case that the two flow terminals are on the outer face of a planar embedding. So simply having separators is not good enough; one needs other ideas to make their techniques work, and the analogues to those other ideas in more general minor-closed families do not seem to be present. Which means that finding a maximum flow algorithm for minor-closed families that is better than the algorithms for arbitrary sparse graphs remains an interesting open problem.

Now, on to planar multiple-source multiple-sink flow. One may well ask, why doesn't one see more papers on flows with multiple sources and sinks? It seems a natural enough variation on the problem. The answer is that, when the class of input graphs is unrestricted and one has multiple sources, one can replace them by a single new source connected by infinite-capacity edges to the previous sources. And similarly multiple sinks can be replaced by a single new sink. So flow with multiple sources and sinks is equivalent to a conventional flow problem with a single source and a single sink in a graph with two new vertices. But of course adding these vertices could destroy planarity. The graphs formed by adding two vertices to a planar graph (the 2-apex graphs) are minor-closed, so if the remark in my paper had been accurate then we would already know how to solve planar multi-terminal flows in time \( O(n^{3/2}\log n) \). But the remark was not accurate and before these papers came out we didn't know how to do that.

Both new papers use cycle separators, and both have a divide-and-conquer strategy in which the "conquer" steps use as a subproblem algorithms for flow in planar graphs with multiple sources and a single sink (or multiple sinks and a single source). This subproblem was solved independently and nearly simultaneously in two other recent arXiv preprints by Borradaile and Wulff-Nilsen (arXiv:1008.4966) and Klein and Mozes (arXiv:1008.5332) and its solution is itself a cycle-separator-based divide and conquer, whose running time is \( O(n^{3/2}\log n) \). In Nussbaum's algorithm, the outer level of divide and conquer multiplies the time by another log factor, while Mozes finds a way of avoiding this penalty.

In a little more detail, Nussbaum uses a weighted separator theorem that allows him to partition the input graph into subgraphs with a number of sources and sinks that decreases by a constant factor at each level of the recursion. Mozes instead uses an unweighted separator theorem that decreases the total number of vertices by a constant factor at each level but that may not evenly split the sources and the sinks.

After dividing the vertices by his separator, Nussbaum finds a maximum flow from the sources on the left side of the separator to the sinks on the right side (by combining a multiple-source single-sink flow from the sources to the separator and a single-source multiple-sink flow from the separator to the sinks, and then reconciling these two flows). The minimum cut corresponding to this maximum flow is itself a good separator, allowing Nussbaum to recurse on each side of the cut. Then he adds the cut edges back to the graph and finds the remaining flow from the sources on the right side of the separator to the sinks on the left (again, by combining multi-source single-sink and single-source multi-sink flow subproblems).

Mozes performs the recursion in a slightly different order: he first finds a maximum flow in each subproblem, and then finds and reconciles maximum flows from the subproblems to the separator vertices and vice versa. By doing things in this order, he avoids having to find a cut that is a good separator, allowing him to use unweighted separators. So he gets a time that can be analyzed by something resembling the recurrence \( T(n) = 2T(n/2) + O(n^{3/2}\log n) \), which solves to \( O(n^{3/2}\log n) \) without any additional logs.

As well as being interesting for their algorithmic results, to me this sequence of papers is interesting as a case study of the speed-up in research made possible by preprint services such as the arXiv. If Nussbaum had to wait for one conference reviewing cycle to find out about the multiple-source single-sink papers that he needed for his result, and then Mozes had to wait for another cycle for Nussbaum's paper to come out before he could improve it, it would all have taken a much longer time. And the mistake in my own paper could have made the delay even longer, by tricking some conference program committee members into thinking Nussbaum and Mozes' results were already known. Because of the arXiv, these unnecessary delays can be avoided, speeding the pace of research.

---

Comments: