TY - UNPB

T1 - Minimum Cycle Basis and All-Pairs Min Cut of a Planar Graph in Subquadratic Time.

AU - Wulff-Nilsen, Christian

PY - 2009

Y1 - 2009

N2 - A minimum cycle basis of a weighted undirected graph G is a ba-sis of the cycle space of G such that the total weight of the cycles inthis basis is minimized. If G is a planar graph with non-negative edgeweights, such a basis can be found in O(n2) time and space, where nis the size of G. We show that this is optimal if an explicit represen-tation of the basis is required. We then present an O(n3/2 log n) timeand O(n3/2) space algorithm that computes a minimum cycle basisimplicitly. From this result, we obtain an output-sensitive algorithmthat explicitly computes a minimum cycle basis in O(n3/2 log n + C)time and O(n3/2 + C) space, where C is the total size (number ofedges and vertices) of the cycles in the basis. These bounds reduceto O(n3/2 log n) and O(n3/2), respectively, when G is unweighted. Weget similar results for the all-pairs min cut problem since it is dualequivalent to the minimum cycle basis problem for planar graphs.We also obtain O(n3/2 log n) time and O(n3/2) space algorithms forfinding, respectively, the weight vector and a Gomory-Hu tree of G.The previous best time and space bound for these two problems wasquadratic. From our Gomory-Hu tree algorithm, we obtain the fol-lowing result: with O(n3/2 log n) time and O(n3/2) space for prepro-cessing, the weight of a min cut between any two given vertices of Gcan be reported in constant time. Previously, such an oracle requiredquadratic time and space for preprocessing. The oracle can also beextended to report the actual cut in time proportional to its size.

AB - A minimum cycle basis of a weighted undirected graph G is a ba-sis of the cycle space of G such that the total weight of the cycles inthis basis is minimized. If G is a planar graph with non-negative edgeweights, such a basis can be found in O(n2) time and space, where nis the size of G. We show that this is optimal if an explicit represen-tation of the basis is required. We then present an O(n3/2 log n) timeand O(n3/2) space algorithm that computes a minimum cycle basisimplicitly. From this result, we obtain an output-sensitive algorithmthat explicitly computes a minimum cycle basis in O(n3/2 log n + C)time and O(n3/2 + C) space, where C is the total size (number ofedges and vertices) of the cycles in the basis. These bounds reduceto O(n3/2 log n) and O(n3/2), respectively, when G is unweighted. Weget similar results for the all-pairs min cut problem since it is dualequivalent to the minimum cycle basis problem for planar graphs.We also obtain O(n3/2 log n) time and O(n3/2) space algorithms forfinding, respectively, the weight vector and a Gomory-Hu tree of G.The previous best time and space bound for these two problems wasquadratic. From our Gomory-Hu tree algorithm, we obtain the fol-lowing result: with O(n3/2 log n) time and O(n3/2) space for prepro-cessing, the weight of a min cut between any two given vertices of Gcan be reported in constant time. Previously, such an oracle requiredquadratic time and space for preprocessing. The oracle can also beextended to report the actual cut in time proportional to its size.

M3 - Working paper

SP - 1

EP - 47

BT - Minimum Cycle Basis and All-Pairs Min Cut of a Planar Graph in Subquadratic Time.

ER -