### Cycle Bases of (Directed) Graphs

Participants: |
Christian Liebchen, Rolf H. Möhring, Gregor Wünsch |

Cooperation with: |
Ekkehard Köhler, Leon Peeters, Romeo Rizzi |

#### Abstract:

For a directed graph *D*, having *n* nodes and *m* arcs,
an *m*-dimensional vector belongs to its *cycle space*,
if it is a linear combination of -1,0,1-incidence vectors of not
necessarily directed cycles of *D*.

There are at least two well-known classes of bases for the cycle space of a directed graph:

- bases which project onto a cycle basis for the underlying undirected graph of
*D*and - bases whose elements are induced by the chords of some spanning tree of
*D*.

Though they have been introduced already in Whitney's
1935 initial publication on Matroids, generalized
fundamental cycle bases are less known. But they are
not the only forgotten class *in-between* the
two most popular classes: Especially for periodic
timetabling, *integral cycle bases* are of
particular interest.

The relationship between the various classes of cycle
bases of directed graphs, as well
as their characterizations, becomes very clear by
investigating their *cycle matrices*, i.e. their
arc-cycle incidence matrices. In particular the
definition of the *determinant of a cycle basis*
serves this purpose.

In periodic timetabling, one is interested in finding a short integral cycle basis with respect to given weights for the arcs. Whereas optimization can be performed in polynomial time for both general directed cycle bases and bases which project onto cycle bases for the underlying undirected graph, optimization is APX-hard for fundamental cycle bases, both in the strict and weak sense, thus in particular unlikely to become well-approximated. In turn, in 2008 the complexity of minimizing over the class integral cycle bases is open.

#### See also:

**Workshop**In May 2008, together with Tübingen University we co-organized an international Workshop dedicated to Cycle and Cut Bases.**Publications**C. Liebchen and G. Wünsch:*The Zoo of Tree Spanner Problems*, Discrete Applied Mathematics**156**(5), pages 569-587, 2008C. Liebchen, G. Wünsch, E. Köhler, A. Reich, and R. Rizzi:*Benchmarks for Strictly Fundamental Cycle Bases*, Springer LNCS Proceedings of WEA 2007C. Liebchen and R. Rizzi:*Classes of Cycle Bases*, Discrete Applied Mathematics**155**(3), pages 337-355, 2007C. Liebchen and R. Rizzi:*A Greedy Approach to Compute a Minimum Cycle Bases of a Directed Graph*, Information Processing Letters**94**(3), pages 107-112, 2005C. Liebchen:*Finding Short Integral Cycle Bases for Cyclic Timetabling*, Springer LNCS Proceedings of ESA 2003C. Liebchen and L. Peeters:*On Cyclic Timetabling and Cycles in Graphs*, 2002**Projects**