Efficient deterministic algorithms for finding optimal cycle bases in undirected graphs

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.

In un grafo G, semplice e non orientato, un ciclo (generalizzato) corrisponde a un sottografo in cui ogni nodo ha un numero pari di lati incidenti. Tutti i cicli di un grafo formano uno spazio vettoriale in GF(2), il cosiddetto spazio dei cicli, e una base di questo spazio, vale a dire una base di cicli, restituisce una rappresentazione compatta della struttura ciclica di G. In una serie di applicazioni, come per esempio l'analisi di circuti elettrici, la progettazione di reti, la schedulazione di eventi periodici, la biologia computazionale e la chimica organica, abbiamo un grafo G con un peso non negativo su ogni lato e siamo interessati a determinare una base di cicli minima, vale a dire una base di peso totale minimo, dove il peso di una base (ciclo) è definito come la somma dei pesi dei suoi cicli (lati). Il principale obiettivo della tesi è quello di progettare algoritmi deterministici efficienti per il problema di determinare una base di cicli minima. Il nostro interesse risiede nel miglioramento sia della complessità nel caso peggiore sia delle reali prestazioni su un esteso insieme di istanze. Punto di partenza è l'analisi dei principali algoritmi deterministici noti in letteratura, con i rispettivi punti di forza e di debolezza. Un framework computazionale unificato viene proposto e usato per un dettagliato studio comparativo. Sulla base di questa analisi, la strategia scelta è quella di generare un insieme di cicli candidati dal quale una base di cicli minima è ricavata tramite un test d'indipendenza lineare. Introduciamo quindi il concetto di ciclo isometrico che porta a un insieme compatto di cicli candidati, caratterizziamo questo insieme e descriviamo una procedura efficiente per generarlo. Studiamo anche un'ulteriore riduzione del numero dei cicli candidati, mostrando che l'insieme dei cicli isometrici raggiunge il miglior compromesso tra la dimensione dell'insieme dei cicli candidati e il corrispondente tempo impiegato per la generazione. Restrigendo l'attenzione all'insieme dei cicli isometrici, proponiamo due efficienti algoritmi deterministici. Progettiamo prima un test d'indipendenza che sfrutta la caratterizzazione dei cicli isometrici e usa una tecnica di bit packing. Il risultante algoritmo in O(m^2 n / log n) si rivela il migliore dal punto di vista dell'analisi del caso peggiore. Proponiamo poi un test d'indipendenza le cui scelte adattative mirano a evitare operazioni non necessarie, che porta a un efficiente algoritmo chiamato AICE (Adaptive Isometric Cycles Extraction). Risultati computazionali mostrano che AICE supera i precedenti algoritmi di uno o due ordini di grandezza su istanze di medie dimensioni e permette di ottenere una soluzione ottima anche per instanze di grandi dimensioni in un tempo ragionevole. Studiamo anche due varianti del problema con vincoli strutturali aggiuntivi che risultano di interesse in alcune applicazioni, come l'analisi di circuiti elettrici e la progettazione di reti. Nella prima variante, ogni lato ha una lunghezza non negativa e vogliamo determinare una base di cicli minima con cicli di lunghezza limitata, vale a dire tale che la lunghezza di ogni ciclo non superi una data costante. Proviamo che il problema è NP-difficile e progettiamo un semplice schema di approssimazione pienamente polinomiale. Mostriamo che il caso speciale in cui tutti i lati hanno uguale lunghezza è risolvibile in tempo polinomiale e l'algoritmo che proponiamo ha la stessa complessità nel caso peggiore di quello descritto precedentemente per il caso senza il vincolo aggiuntivo sulla lunghezza dei cicli. Nella seconda variante, a ogni lato è assegnato un limite non negativo e desideriamo determinare una base di cicli di modo che ciascun lato appartenga a un numero di cicli della base non maggiore del suo limite. Proviamo che è NP-completo decidere se una tale base esiste e proponiamo un'euristica costruttiva che mira a minimizzare la violazione massima, vale a dire per ogni lato il numero di cicli oltre il limite che lo contengono.