A POLYNOMIAL-TIME ALGORITHM TO FIND THE SHORTEST CYCLE BASIS OF A GRAPH

Define the length of a basis of the cycle space of a graph to be the sum of the lengths of all cycles in the basis. An algorithm is given that finds a cycle basis with the shortest possible length in O(m**3n) operations, where m is the number of edges and n is the number of vertices. This is the first known polynomial-time algorithm for this problem. Edges may be weighted or unweighted. Also, the shortest cycle basis is shown to have at most 3(n-1)(n-2)/2 edges for the unweighted case. An O(mn**2) algorithm to obtain a suboptimal cycle basis of length O(n**2) for unweighted graphs is also given.