Union of all the minimum cycle bases of a graph (Q1378498)

Summary: The perception of cyclic structures is a crucial step in the analysis of graphs. To describe the cycle vector space of a graph, a minimum cycle basis can be computed in polynomial time using an algorithm of \textit{J. D. Horton} [SIAM J. Comput. 16, No. 2, 358-366 (1987; Zbl 0632.68064)]. But the set of cycles corresponding to a minimum basis is not always relevant for analyzing the cyclic structure of a graph. This restriction is due to the fact that a minimum cycle basis is generally not unique for a given graph. Therefore, the smallest canonical set of cycles which describes the cyclic structure of a graph is the union of all the minimum cycle bases. This set of cycles is called the set of relevant cycles and denoted by \({\mathcal C}_R\). A relevant cycle can also be defined as a cycle which is not the sum of shorter cycles. A polynomial algorithm is presented that computes a compact representation of the potentially exponential-sized set \({\mathcal C}_R\) in \(O(\nu m^3)\) (where \(\nu\) denotes the cyclomatic number). This compact representation consists of a polynomial number of relevant cycle prototypes from which all the relevant cycles can be listed in \(O(n |{\mathcal C}_R|)\). A polynomial method is also given that computes the number of relevant cycles without listing all of them.