|Thesis abstract: |
Given a simple undirected graph G, a (generalized) cycle corresponds to a subgraph in which every node has an even number of incident edges. All cycles of a graph form a vector space over GF(2), the so-called cycle space, and a basis of this space, i.e., a cycle basis, provides a compact representation of the cyclic structure of G.
In a variety of applications, e.g., analysis of electrical circuits, network design, periodic event scheduling, computational biology and organic chemistry, we are given a graph G with a nonnegative weight assigned to each edge and we are interested in finding a minimum cycle basis, i.e., a cycle basis of minimum total weight, where the weight of a basis (cycle) is defined as the sum of the weights of its cycles (edges).
The main goal of the thesis is to devise efficient deterministic algorithms for the minimum cycle basis problem. Our interest is to improve on the best worst-case complexity as well as on the actual performance over an extensive range of instances.
We start by analysing the main deterministic algorithms proposed in the literature and by pointing out the respective strength and weakness. A unified computational framework is proposed and used for a detailed comparative study.
Based on this analysis, we adopt the general strategy of generating a set of candidate cycles from which a minimum cycle basis is extracted by a linear independence test. We introduce the concept of isometric cycle that gives rise to a very compact set of candidate cycles. We provide a full characterization of this set and describe an efficient procedure for generating it. We also investigate further reduction of the number of candidate cycles, but we show that the set of isometric cycles achieves the best tradeoff between the size of the set of candidate cycles and the related generation time.
By restricting attention to the set of isometric cycles we propose two efficient deterministic algorithms.
First, we devise an independence test exploiting the characterization of isometric cycles and using a bit packing technique. The overall resulting O(m^2 n / log n) algorithm turns out to be the best one from the worst-case complexity point of view.
Then, we propose an independence test whose adaptive choices aim at avoiding unnecessary operations, which leads to a very efficient Adaptive Isometric Cycles Extraction algorithm (AICE). Computational results show that AICE outperforms the previous algorithms by one or two order of magnitude on medium-size instances and allows to obtain an optimal solution also for large-size instances in a reasonable time.
We also investigate two variants of the minimum cycle basis problem with additional structural constraints that are of interest in some applications, such as the analysis of electrical circuits and network design.
In the first variant, a nonnegative length is assigned to each edge and we look for a minimum cycle basis with cycles of bounded length, i.e., such that the length of each cycle does not exceed a given constant. We prove that the general problem is NP-hard and we devise a simple fully polynomial-time approximation scheme (FPTAS). We show that the special case where all edges have equal length is polynomially solvable and the algorithm that we propose has the same worst-case complexity as the one for the unconstrained minimum cycle basis problem.
In the second variant, a nonnegative bound is assigned to each edge and we wish to find a cycle basis with limited edge overlap, i.e., such that each edge belongs to a number of cycles of the basis not greater than its prescribed bound. We prove that it is NP-complete to decide whether such a cycle basis exists and we propose a constructive heuristic aiming at minimizing the maximum bound violation, i.e., the excess for each edge of the number of cycles containing it over its bound.