On applying separator decompositions to path problems and network flow

Abstract

Separator decompositions have proven to be useful for efficient parallel shortest- path computation. In this paper the applicability of separator decompositions to maximum ow computation is explored. It is shown that efficient 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.