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 {0,1} incidence vector is associated with each cycle and the vector space over

$\mathbb{F}_2$

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 an approximate minimum cycle basis. For any integer

k

 ≥ 1, we give (2

k

 − 1)-approximation algorithms with expected running time

O

(

k

m

n

1 + 2/

k

 + 

m

n

(1 + 1/

k

)(

ω

 − 1)

) and deterministic running time

O

(

n

3 + 2/

k

), respectively. Here

ω

is the best exponent of matrix multiplication. It is presently known that

ω

 < 2.376. Both algorithms are

o

(

m

ω

) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the

Θ

(

m

ω

) bound.

We also present a 2-approximation algorithm with

$O(m^{\omega}\sqrt{n\log n})$

expected running time, a linear time 2-approximation algorithm for planar graphs and an

O

(

n

3

) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.