A greedy approach to compute a minimum cycle basis of a directed graph

Given a directed graph D = (V, A), we consider its cycle space C[D] , i.e. the vector subspace of Q|A| spanned by the incidence vectors of the oriented cycles of D. An oriented cycle of D is just any cycle of the underlying undirected graph of D along with an orientation; its incidence vector is 0 on the arcs not included, while, for the included arcs, it is +1 on the arcs oriented according to the orientation and −1 on the arcs going backward. Assume a nonnegative weight w_a ∈ R+ is associated to each arc a of D. We can extend the weighting w to subsets F of A and to families F of such subsets by defining w(F ) := f ∈F w(f ) and w(F) := F ∈F w(F ). Given the pair (D, w), we are interested in computing a minimum weight basis of C[D]. This problem is strongly related to the classical problem of computing a minimum cycle basis of an undirected graph. In 1987, Horton developed the first polynomial time algorithm for computing a minimum cycle basis of an undirected graph. As for directed graphs, the first algorithm for computing a minimum directed cycle basis is due to Kavitha and Mehlhorn. Its asymptotic complexity is O(m^4 n). In this paper, we show how the original approach of Horton can be actually pur- sued also in the context of directed graphs, while retaining its simplicity. This both allows for a practical O(m^4 n) adaptation of Horton’s original algorithm requiring only minor modifications in the actual code and for a more involved O(m^{ω+1} n) solution. At the end, we discuss the applicability of this approach to more spe- cialized classes of directed cycle bases, namely, integral cycle bases and generalized fundamental cycle bases.