Refine
Language
- English (4)
Keywords
- approximation algorithms (1)
- cycle basis (1)
- graph algorithms (1)
- metric approximation (1)
Application Area
- B (3)
Given a directed graph D = (V;A), we consider its cycle space CD, i.e. the vector
subspace of Q|A| spanned by the incidence vectors of the oriented cycles of D. An
oriented cycle of D is just any cycle of the underlying undirected graph of D along
with an orientation; its incidence vector is 0 on the arcs not included, while, for the
included arcs, it is +1 on the arcs oriented according to the orientation and -1 on
the arcs going backward. Assume a nonnegative weight wa ? R+ is associated to
each arc a of D. We can extend the weighting w to subsets F of A and to families F
of such subsets by dening w(F) := ?f?F w(f) and w(F) := ?F?F w(F). Given
the pair (D;w), we are interested in computing a minimum weight basis of CD.
This problem is strongly related to the classical problem of computing a minimum
cycle basis of an undirected graph. In 1987, Horton developed the first polynomial
time algorithm for computing a minimum cycle basis of an undirected graph. As for
directed graphs, the first algorithm for computing a minimum directed cycle basis
is due to Kavitha and Mehlhorn. Its asymptotic complexity is ~O (m4n).
In this paper, we show how the original approach of Horton can be actually pursued
also in the context of directed graphs, while retaining its simplicity. This both
allows for a practical ~O(m4n) adaptation of Horton's original algorithm requiring
only minor modifications in the actual code and for a more involved ~O(mw+1n)
solution. At the end, we discuss the applicability of this approach to more specialized
classes of directed cycle bases, namely, integral cycle bases and generalized
fundamental cycle bases.
Classes of Cycle Bases
(2005)
In the last years, new variants of the minimum cycle basis (MCB)
problem and new classes of cycle bases have been introduced, as motivated
by several applications from disparate areas of scientific and technological
inquiries. At present, the complexity status of the MCB problem has been
settled only for undirected, directed, and strictly fundamental cycle bases.
In this paper, we over an unitary classification accommodating these
3 classes and further including the following 4 relevant classes: 2-bases (or
planar bases), weakly fundamental cycle bases, totally unimodular cycle
bases, and integral cycle bases. The classification is complete in that, for
each ordered pair (A;B) of classes considered, we either prove that A ? B
holds for every graph or provide a counterexample graph for which A ? B.
The seven notions of cycle bases are distinct (either A ? B or B ? A is
exhibited for each pair (A;B)).
All counterexamples proposed have been designed to be ultimately effective
in separating the various algorithmic variants of the MCB problem
naturally associated to each one of these seven classes. We even provide
a linear time algorithm for computing a minimum 2-basis of a graph. Finally,
notice that the resolution of the complexity status of some of the
remaining three classes would have an immediate impact on practical applications,
as for instance in periodic railway timetabling, only integral
cycle bases are of direct use.
Based on a recent work by Abraham, Bartal and Neiman (2007), we construct a strictly fundamental cycle basis of length O(n2) for any unweighted graph, whence proving the conjecture of Deo et al. (1982).
For weighted graphs, we construct cycle bases of length O(W log(n) log(log(n))), where W denotes the sum of the weights of the edges. This improves the upper bound that follows from the result of Elkin et al. (2005) by a logarithmic factor and, for comparison from below, some natural classes of large girth graphs are known to exhibit minimum cycle bases of length Ω(W log(n)).
We achieve this bound for weighted graphs by not restricting ourselves to strictly fundamental cycle bases - as it is inherent to the approach of Elkin et al. - but rather also considering weakly fundamental cycle bases in our construction. This way we profit from some nice properties of Hierarchically Well-Separated Trees that were introduced by Bartal (1998).
In the Minimum Strictly Fundamental Cycle Basis (MSFCB) problem one is looking for a spanning tree such that the sum of the lengths of its induced fundamental circuits is minimum.
We identify square planar grid graphs as being very challenging testbeds for the MSFCB. The best lower and upper bounds for this problem are due to Alon, Karp, Peleg, and West (1995) and to Amaldi et~al. (2004).
We improve significantly their bounds, both empirically and asymptotically. Ideally, these new benchmarks will serve as a reference for the performance of any new heuristic for the MSFCB problem which will be designed only in the future.