An Õ(m 2 n) Randomized Algorithm to Compute a Minimum Cycle Basis of a Directed Graph

We consider the problem of computing a minimum cycle basis in a directed graph

G

. The input to this problem is a directed graph whose arcs have positive weights. In this problem a {–1,0,1} incidence vector is associated with each cycle and the vector space over

${\mathbb Q}$

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 weights of the cycles is minimum is called a minimum cycle basis of

G

. The current fastest algorithm for computing a minimum cycle basis in a directed graph with

m

arcs and

n

vertices runs in

$\tilde{O}(m{^{\omega+1}}n)$

time (where

ω

< 2.376 is the exponent of matrix multiplication). If one allows randomization, then an Õ(

m

3

n

) algorithm is known for this problem. In this paper we present a simple Õ(

m

2

n

) randomized algorithm for this problem.

The problem of computing a minimum cycle basis in an

undirected

graph has been well-studied. 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 the graph. The fastest known algorithm for computing a minimum cycle basis in an undirected graph runs in

O

(

m

2

n

+

mn

2

log

n

) time and our randomized algorithm for directed graphs almost matches this running time.