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 {C1,…,Ck} 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 {C1,…,Ck} is weakly fundamental if for every i there is an arc ai such that Ci(ai)=±1 while Cj(ai)=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.