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:

The elements of the second class are called (strictly) fundamental cycle bases, which are obviously a subclass of the cycle bases projecting onto cycle bases for the underlying undirected graph.

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.

Map of Directed Cycle Bases

See also: