A New Bound on the Length of Minimum Cycle Bases

Romeo Rizzi and Christian Liebchen

Combinatorial optimization, Minimum cycle basis problem, weakly fundamental cycle bases, tree metrics

For any weighted graph we construct a cycle basis of length O(W*log(n)*log(log(n))), where W denotes the sum of the weights of the edges. This improves the upper bound that was obtained only recently by Elkin et al. (2005) by a logarithmic factor. From below, our result has to be compared with Ω(W*log(n)), being the length of the minimum cycle bases (MCB) of a class of graphs with large girth.

We achieve this bound by not restricting ourselves to strictly fundamental cycle bases - as it is inherent to the approach of Elkin et al. - but rather also considering weakly fundamental cycle bases in our construction. This way, we can take profit of some nice properties of Hierarchically Partitioned Metrics (HPM) as they have been introduced by Bartal (1998).

Download as [PDF] [ps.gz]