Cycle Bases in Graphs

  The first part concentrates on new structural results which might help to decide if the minimum weight cycle basis problem (MCB) for   integral and totally unimodular bases is in P or is NP-complete. A new potentially useful class of double cover bases is also presented. The   main reason for research in this area is the fact that known algorithms   for finding MCBs in general graphs return bases with rather poor   theoretical properties.

  In the second part we present an algorithm for computing general   minimum weight cycle bases in time O(E^ω) for general graphs; here V   and E denote the number of nodes and edges, respectively, and ω is the exponent of the fastest matrix multiplication algorithm. Our algorithm is the first to run faster than Õ(E²V). A key ingredient to our improved running time is the insight that the search for the minimum basis can be restricted to a set of candidate cycles of total length O(V E).