On Applying Separator Decompositions to Path Problems and Network Flow

Separator decompositions have proven to be useful for e cient parallel shortest-path computation. In this paper the applicability of separator decompositions to maximum ow computation is explored. It is shown that e cient parallel shortest-path computation can be incorporated in the shortest augmenting path maximum ow algorithm. A class of graphs is described for which the resulting algorithm takes O(n 2+ log n) time and O(n 3) work, where 0 < < 1 3 is a class-dependent constant. For graphs with bounded treewidth an NC-algorithm is known for the maximum ow problem. In this paper we show that width-O(1) tree decompositions and separator decompositions with separators, leaf vertex sets, and boundaries of O(1) size are equivalent notions under NC computation. NC-algorithms are given for converting one type of graph decomposition into the other. Furthermore, the NC-max ow algorithm is restated in the separator decomposition framework.