Efficient deterministic algorithms for finding optimal cycle bases

Given a simple undirected graph G, a (generalized) cycle corresponds to a subgraph in which every node has an even number of incident edges. All cycles of a graph form a vector space over GF(2), the so-called cycle space, and a basis of this space, i.e., a cycle basis, provides a compact representation of the cyclic structure of G. In a variety of applications, e.g., analysis of electrical circuits, network design, periodic event scheduling, computational biology and organic chemistry, we are given a graph G with a nonnegative weight assigned to each edge and we are interested in finding a minimum cycle basis, i.e., a cycle basis of minimum total weight, where the weight of a basis (cycle) is defined as the sum of the weights of its cycles (edges). The main goal of the work is to devise efficient deterministic algorithms for the minimum cycle basis problem. Our interest is to improve on the best worst-case complexity as well as on the actual performance over an extensive range of instances. We also investigate two variants of the minimum cycle basis problem with additional structural constraints that are of interest in some applications.