Properties of Gomory-Hu co-cycle bases
Let D = (V, A) be a directed graph with non-negative arc weights. We study the problem of computing certain special co-cycle bases of D, in particular, a minimum weight weakly fundamental co-cycle basis. A co-cycle in D corresponds to a cut in the underlying undirected graph and a {-1, 0, 1} arc incidence vector is associated with each co-cycle, where the +/-1 coordinates are used for the arcs crossing the cut. The weight of a co-cycle C is the sum of the weights of those arcs a such that C (a) = +/-1. The vector space over Q generated by the arc incidence vectors of the co-cycles is the co-cycle space of D. The co-cycle space of D can also be defined as the orthogonal complement of the cycle space of D. A set of linearly independent co-cycles that span the co-cycle space is a co-cycle basis of D. The problem of computing a co-cycle basis {C-1, ..., C-k} such that the sum of weights of the co-cycles in the basis is the least possible is the minimum co-cycle basis problem. A co-cycle basis {C-1, ..., C-k} is weakly fundamental if for every i there is an arc a(i) such that C-i(a(i)) = +/-1 while C-j(a(i)) = 0 for j > i. The minimum cycle basis problem in directed and undirected graphs is a well-studied problem and while polynomial time algorithms are known for these problems, the problem of computing a minimum weight weakly fundamental cycle basis has recently been shown to be APX-hard. We show that the co-cycle basis corresponding to the cuts of a Gomory-Hu tree T of the underlying undirected graph of D is a minimum weight weakly fundamental co-cycle basis of D. This is, in fact, a minimum co-cycle basis of D and it is also totally unimodular. Thus this is a special co-cycle basis that simultaneously answers several questions in the domain of co-cycle bases. It is known that there is no such special cycle basis for general graphs. (C) 2011 Elsevier B.V. All rights reserved.
co-cycles graphs cuts gomory-hu tree