New approximation algorithms for minimum cycle bases of graphs

We consider the problem of computing an approximate minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a f0;1g incidence vector is associated with each cycle and the vector space over F2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. We present two new algorithms to compute approximate minimum cycle basis. For any inte-ger k ¸ 1, we give (2k¡1)-approximation algorithms with expected running time O(kmn1+2=k + mn(1+1=k)(ω¡1)) and deterministic running time O(n3+2=k), respectively. Here w is the best expo-nent of matrix multiplication. It is presently known that w < 2:376. Both algorithms are o(mω) for dense graphs. This is the rst time that any algorithm which computes sparse cycle bases with a guarantee drops below the Q(mω) bound. We also present a 2-approximation algorithm with running time O(mω p n logn), a linear time 2-approximation algorithm for planar graphs and an O(n3) time 2:42-approximation algorithm for the complete Euclidean graph in the plane