%----------------------------------- CAUTION ---------------------------------------------- % The official, published form of a paper in this Journal is the PostScript file (.ps file). % The .tex file is made available only for the benefit of those who might wish to do text % searches, etc., but the .tex file may not compile properly to produce the published form % of the paper, due to lack of graphics, or due to other macros that may have been used by % the authors and not be made available to the reader. Such graphics or other macros will % not be provided separately by this Journal. %------------------------------------------------------------------------------------------ \documentclass[12pt]{article} \usepackage{float,epic,eepic} \usepackage{newdef} \title{Union of all the minimum cycle bases of a graph} \makeatletter \author{Philippe {\sc Vismara}\\\\ {\normalsize \parbox{0.45\linewidth}{ \begin{center} {\em L.I.R.M.M.\/}\\ {\small Université Montpellier {\sc II} / CNRS}\\ {\small 161 rue Ada,}\\ {\small 34392 Montpellier Cedex 5, {\sc France}}\\ {\small E-mail: vismara@lirmm.fr} \end{center}} \hspace*{0.5cm}\parbox{0.45\linewidth}{ \begin{center} {\em E.N.S.A.-M.\/}\\ {\small 2 Place Pierre Viala}\\ {\small 34060 Montpellier Cedex 1, {\sc France}} {\small E-mail: vismara@ensam.inra.fr} \end{center}}} } \date{} \setlength{\oddsidemargin}{0.25in} \setlength{\evensidemargin}{0.25in} \setlength{\topmargin}{0in} \setlength{\textheight}{9in} \setlength{\textwidth}{6in} % \pagestyle{myheadings} \markright{\textsc{the electronic journal of combinatorics 4 (1997), \#R9}} % \renewcommand{\floatpagefraction}{0.8} \setcounter{totalnumber}{3} \renewcommand{\baselinestretch}{1.1} % \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{definition}{Definition} % \bibliographystyle{named-compact} %============================================================================ \begin{document} \maketitle % \centerline{\small Submited: October 10, 1996; Accepted: January 17, 1997.} \medskip \begin{abstract} 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 [Horton, 1987]. 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 {\em union of all the minimum cycle bases\/}. This set of cycles is called the {\em set of relevant cycles\/} and denoted by ${\cal 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 ${\cal 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\,|{\cal C_R}|)$. A polynomial method is also given that computes the number of relevant cycles without listing all of them. \end{abstract} \medskip \centerline{\small AMS Subject Classification: 05C85 (primary), 05C38 (secondary).} \clearpage %======================================================================================== %======================================================================================== \section*{Introduction} %======================================================================================== For a graph $G=(V,E)$ with $n$ vertices and $m$ edges the set of elementary\footnote{A cycle is called {\em elementary\/} if it contains no vertex more than once.} cycles can be extended to form a vector space on $\{0,1\}^{m}$. If $G$ is connected, the dimension of this vector space is given by the {\em cyclomatic number\/} $\nu = m - n + 1$, initially introduced for polyhedrons by \cite{eul752} and generalized by \cite{cau813}. The simplest way to determine this vector space (denoted by ${\cal C}$) consists in finding a {\em fundamental basis associated with a spanning tree\/}\footnote{Let $T=(V,E')$ be a spanning tree for the graph $G=(V,E)$. Adding any edge from $E \setminus E'$ to $T$ creates a single cycle. The set of cycles generated this way defines a basis for the vector space ${\cal C}$.} \cite{kir847}. Many papers deal with fundamental basis search \cite{welc66,pato69,gibb69}. Most of them use this notion to list all elementary cycles of a graph. Unfortunately, as \cite{mate75} have shown, such a method can generate $2^\nu$ vectors few of which actually correspond to elementary cycles. \cite{read75} solve this problem using a search algorithm which needs $O(n+m+nc)$ operations, where $c$ is the number of elementary cycles. For planar graphs, \cite{sysl81} has shown that a vector space approach can be as efficient as a search algorithm. Because fundamental cycle bases may be numerous, they are compared according to their lengths. The length of a cycle basis is the sum of the lengths of all cycles in the basis. This notion defines {\em minimum fundamental cycle bases\/}. \cite{deo82} have shown that finding a minimum fundamental cycle basis is an NP-complete problem. Furthermore, \cite{hort87} has presented a polynomial time algorithm to find a minimum cycle basis not necessarily associated with a spanning tree. Some applications require the perception of the cyclic parts of a graph. %and their relationships. An obvious solution would be to list all elementary cycles. This method has two drawbacks: it cannot be performed efficiently and only a few of the elementary cycles may be relevant to the application domain. Another solution would be to find a minimum cycle basis, but such a set of cycles is generally not unique for a given graph. Of course, the kind of perception which is to be performed determines the definition of an optimal set of cycles. In general, one requires a canonical set of cycles from which the cycle vector space can be generated. The smallest set satisfying this condition is the {\em union of all the minimum cycle bases\/}. This paper is organized as follows: Section~\ref{alghorton} presents Horton's algorithm to find a minimum cycle basis. Section~\ref{defperti} defines the {\em set of relevant cycles\/} (denoted by ${\cal C_R}$) as the {\em union of all the minimum cycle bases\/}. We present a polynomial time algorithm to compute ${\cal C_R}$ in terms of a polynomial number of cycle families. These define a partition of ${\cal C_R}$. Each family is represented by a single cycle from which all the other cycles of the family can be directly generated. In the last section, we propose a polynomial method to calculate the number of relevant cycles (for the whole graph or including a given vertex). %====================================-------------------------------------------------- \section{Preliminary} %====================================-------------------------------------------------- In this paper, we consider an undirected 2-connected graph $G=(V,E)$ without loops or multiple edges. Considering 2-connected graphs only does not limit generality because cycle subspaces associated with 2-connected components are independent and complementary (their union is equal to the whole vector space). An edge is denoted by an unordered pair of vertices $(x,y)$. A {\em cycle\/} is a subgraph such that any vertex degree is even. Therefore, we consider a connected cycle as either a set of edges $\{(x_1,x_2), (x_2, x_3),\ldots\}$ or a closed path $(x_1, x_2, x_3, \ldots, x_1)$. An {\em elementary\/} cycle is a minimal subgraph such that every node has degree 2. Define the {\em sum\/} of two cycles $C + C'$ to be the symmetric set difference \linebreak $(C\,\cup\,C') \setminus (C\,\cap\,C')$. Then, the cycle vector space is the additive closure of the set of elementary cycles. A cycle $C$ can be represented by an element of the cycle vector space $\{0,1\}^m$ (i.e. $C[i] = 1 \Leftrightarrow edge\ i\ belongs\ to\ C$). For any vertex $v$ in $V$, we denote by $\deg(v)$ the degree of $v$ in $G$ and by $\Gamma(v)$ the set of vertices which are adjacent to $v$. Each edge $e$ is weighted with a real positive number $w(e)$. The weight of any path (or cycle) $\mu = (x_1, x_2, \ldots, x_k)$ is defined by $w(\mu) = \sum_{i\in [1..k-1]} w(\,(x_i, x_{i+1})\,)$. The {\em distance\/} $d(x,y)$ between vertices $x$ and $y$ is the weight of any shortest path from $x$ to $y$. %====================================-------------------------------------------------- \section{Horton's algorithm} \label{alghorton} %====================================-------------------------------------------------- The algorithm proposed by \cite{hort87} is the first polynomial algorithm that finds a minimum cycle basis. In fact, a quite similar method was presented by \cite{sork85}, but Sorkau did not analyze the complexity of his algorithm. Hence, we will only focus on Horton's algorithm which is based on the following theorem: % \Ttheorem{\label{theohorton} Let $x$ be any vertex of any cycle $C$ in a minimum cycle basis. There is an edge $(y,z)$ in $C$ such that $C$ consists of a shortest path from $x$ to $y$, a shortest path from $x$ to $z$ and the edge $(y,z)$.} Note that any cycle satisfying this property does not necessarily belong to a minimum basis. Therefore, Horton's algorithm extracts a cycle basis from an initial set of cycles (denoted by ${\cal C_I}$) satisfying Theorem~\ref{theohorton}: % \setlength{\largeuralgo}{1.0em} \begin{algorithme} \nla $\forall a,b \in V$ find a shortest path $P(a,b)$ between $a$ and $b$.\\ \nba {\sf For} all $v \in V$ {\sf do}:\\ \sba {\sf For} all $(x,y) \in E$ {\sf do}:\\ \sla {\sf If} $P(v,x) \cap P(v,y) = \{v\}$ \\ \sla {\sf Then} add to ${\cal C_I}$ the cycle $C = P(v,x) + P(v,y) + (x,y)$\\ \fba \fba \nla Order the initial set of cycles ${\cal C_I}$ by weight\\ \nla Use a greedy algorithm to extract a minimum cycle basis from ${\cal C_I}$. \end{algorithme} The first step of the algorithm chooses a unique shortest path for every pair of vertices. It can be performed in $O(n^3)$ using different algorithms \cite{floy62,dijk59}. Horton has proved that any choice can lead to an initial set ${\cal C_I}$ including a minimum cycle basis. This proof consists in replacing the cycles of any minimum basis by cycles belonging to ${\cal C_I}$. In the second stage, a cycle $C$ may be created as many times as it contains vertices. To avoid this duplication, Horton uses the method suggested by \cite{tier70}. Considering an order $\pi$ on vertices, all cycles generated from vertex $v$ must only contain vertices that precede $v$ in order~$\pi$. Given a vertex $v$ and an edge $(x,y)$, testing ``$P(v,x) \cap P(v,y) = \{v\}$'' is necessary to check if the corresponding cycle $C$ is {\em degenerate\/} (i.e. at least one vertex of the associated subgraph has a degree equal to 1 or greater than 2). This test needs $O(n)$ operations. So, the second step of Horton's algorithm takes $O(n^2\, m)$ operations. The last step of the algorithm processes ${\cal C_I}$ in order of the weight of the cycles. A new cycle is added to the $k$ cycles of the current partial basis when the new induced set is independent. This test uses a Gaussian elimination on the $m \times (k+1)$ boolean matrix corresponding to the set of cycles (each row is a vector of $\{0,1\}^m$, representing a cycle). The elimination can be performed in $O(m \times (k+1))$. Since $k \leq \nu$ and ${\cal C_I}$ contains at most $\nu n$ cycles\footnote{In step~2, a cycle is added to ${\cal C_I}$ when it consists of two distinct shortest paths. Hence, the number of cycles created from a vertex $v$ is at most equal to the number of cycle closure edges.}, a minimum cycle basis can be found in $O(m {\nu}^2 n)$ operations. %======================================================================================== \section{Union of the all minimum cycle bases}\label{defperti} %======================================================================================== A minimum cycle basis is a compact representation of the cycle vector space of a graph. However, it does not necessarily include all cycles relevant to a given problem. In Organic Chemistry, the constitution of a chemical compound can be viewed as a labeled graph. The perception of cyclic parts is of fundamental importance in the analysis of molecules. Most of the programs dealing with chemistry require a fast and accurate method for the identification of the ``chemically meaningful'' cycles among the potentially large number of elementary cycles embedded in the molecular graph. The most commonly used restriction is a minimum cycle basis. Indeed, for a cycle to be {\em chemically relevant\/}, it must not be the sum of smaller cycles. However, in general, a given graph has several minimum bases. Therefore the above definition of chemically relevant cycles is not satisfactory. For example, the graph presented in Figure~\ref{basext2} has three different minimum bases. \begin{figure} \begin{center} \input{basext3-2.eepic} \end{center} \caption{\label{basext2} An example of a graph having several minimum bases. } \end{figure} The smallest generating set of cycles which is unique for a given graph is the \textit{\textbf{union of all the minimum bases}\/} of the graph. \Tdefinition{A cycle is said to be \textit{\textbf{relevant\/}} if it belongs to at least one minimum cycle basis.} So, the {\em set of relevant cycles}, denoted by ${\cal C_R}$, is the union of all the minimum cycle bases of the graph. Another characterization of relevant cycles is given by the following lemma: \Tlemma{\label{defperti2} $\ C \in {\cal C}$ is {\em relevant\/} \hspace{0.3em} $\Leftrightarrow$\hspace{0.3em} no elementary cycles $C_1, \ldots , C_k$ exist such that $C = C_1 + \ldots + C_k$ and\/ $\forall i \in [1..k],\ w(C_i) < w(C)$. } % {\sl\small \begin{quotation} \noindent{\bf Proof } If $C$ belongs to a minimum cycle basis then it cannot be the sum of shorter cycles. Otherwise, $C$ could be exchanged by one of these cycles in the minimum basis. Conversely, let ${\cal B}$ be a minimum cycle basis and $C$ a cycle which is not the sum of shorter cycles. Then $C = B_1 + \ldots + B_k$, where $\forall i, B_i \in {\cal B}$, and there is at least one cycle $B_i$ such that $w(B_i) \geq w(C)$. Since ${\cal B}$ is a minimum basis, we have $w(B_i) = w(C)$. So, the set $({\cal B} \setminus \{B_i\})\,\cup\,\{C\}$ is a minimum basis $\Box$ \end{quotation}} This definition of cycle relevance has been suggested by \cite{plot71} in the domain of computational chemistry. Since no efficient algorithm was proposed to find these cycles, many works deal with the definition of extended minimum cycle bases which are generally not canonical (see \cite{down89}). The cardinality of the union of the minimum cycle bases is not necessarily polynomial. If $G$ is a complete graph, the cardinality of ${\cal C_R}$ is equal to the polynomial number of 3-edge cycles. But some graphs can include an exponential number of {\em relevant\/} cycles, such as the one given in Figure~\ref{contreperti}. \begin{figure}[h] \begin{center} \input{contreperti2.eepic} \vspace*{-1.5em} \end{center} \caption{\label{contreperti}\sl The union of all the minimum cycle bases of this graph includes $2^{\frac{n}{4}}$ cycles with $\frac{3n}{4}$ vertices $(\ (x,b,u,v,d,w,\ldots,y,x),\ (x,a,u,v,d,w,\ldots,y,x),$ etc.).} \end{figure} The existence of such graphs must not hide the interest of the {\em relevance\/} notion. Firstly, because in some domains, such as organic chemistry, graphs with an exponential number of {\em relevant\/} cycles are almost impossible. Secondly, we present a polynomial time algorithm to compute ${\cal C_R}$ as a polynomial number of parts. Each part corresponds to a {\em family\/} of cycles which can be directly listed from a particular relevant cycle. This cycle defines a {\em prototype\/} of its family. Representing ${\cal C_R}$ as a polynomial number of cycle prototypes provides a way of determining the cardinality of ${\cal C_R}$ in polynomial time. In section~\ref{NumberFam}, we present a method to find the number of cycles which can be generated from a given prototype, without calculating any of them. This compact representation of ${\cal C_R}$ gives a more precise description of the cycle vector space than a simple minimum basis. For instance, in the graph of Figure~\ref{contreperti}, apart from the $\frac{n}{4}$ 4-edge cycles that must be known, the other {\em relevant\/} cycles can be described by a single family. The prototype of this family is one of the $2^{\frac{n}{4}}$ elementary cycles with $\frac{3n}{4}$ vertices. Listing all these {\em relevant\/} cycles is not very meaningful for such a graph. But it can be very useful for a computer system to be able to perceive them and designate a single prototype. Of course, the compact representation can always be replaced by a complete enumeration of the relevant cycles. It provides a canonical set of shortest cycles from which the whole vector space can be generated. %==================================== \section{Partition of the set of relevant cycles ${\cal C_R}$}\label{defpartfam} %==================================== This section defines a partition of the set of relevant cycles such that the number of parts is polynomial. \Tlemma{\label{subpath}If $\mu$ is a subpath of a relevant cycle $C$ such that $w(\mu) \leq \frac{1}{2} w(C)$ then $\mu$ is a shortest path.} % {\sl\small \begin{quotation} \noindent{\bf Proof } Since $C$ is relevant, it belongs to at least one minimum cycle basis ${\cal B}$. Assume that $\mu$ is not a shortest path. Then $\mu$ includes a subpath $\rho = (a \ldots b)$ such that $w(\rho) > d(a,b)$ and there is a shortest path $\rho'$ from $a$ to $b$ such that $\rho$ and $\rho'$ are disjoint. Replacing $\rho$ with $\rho'$ in $C$ will create a new cycle $C'$ such that $w(C') < w(C)$. Define $C''$ to be the cycle that consists of $\rho$ and $\rho'$. Since $w(\rho') < w(\rho) \leq \frac{1}{2} w(C)$, $w(C'') < w(C)$. Because $C = C' + C''$, $C$ can be exchanged for either $C'$ or $C''$ in ${\cal B}$. So ${\cal B}$ cannot be a minimum basis $\Box$ \end{quotation}} In the rest of the paper, we assume that the vertices of the graph being considered are ordered by a numbering $\pi$. This ordering can be chosen arbitrarily. For any cycle $C$ being considered, we denote by $r$ the greatest vertex in $C$ according to $\pi$. \smallskip \Tdefinition{any cycle $C$ is ``\bi{even\/}'' if it consists of two disjoint paths $\mu_1$ and $\mu_2$\\ from $r$ to $x$, such that $r$ is the greatest vertex in $C$ (i.e. $\pi(r) = \max_{z\in C} \pi(z)$)\\ and $w(\mu_1) = w(\mu_2) = \frac{1}{2} w(C)$.\ Otherwise, $C$ is ``\bi{odd\/}''.} \begin{center} \vspace*{-1ex} \input{defoddeven.eepic} \vspace*{-1ex} \end{center} \Ttheorem{\label{theoxpq}any relevant cycle $C$ consists of two disjoint shortest paths $(r \ldots p)$ and $(r \ldots q)$ linked by the edge $(p,q)$ if $C$ is {\em odd\/} or by the path $(p,x,q)$ if $C$ is {\em even}. } % {\sl\small \begin{quotation} \noindent{\bf Proof } If $C$ is even, $C$ consists of two disjoint paths $(r, \ldots, p, x)$ and $(r, \ldots, q, x)$ whose weight is $ \frac{1}{2} w(C)$. Hence, $w(\,(r, \ldots p)\,) \leq \frac{1}{2} w(C)$ and $w(\,(r, \ldots q)\,) \leq \frac{1}{2} w(C)$, because the valuation is positive.\ If $C$ is odd, $C = (r, \ldots p, q, \ldots, r)$ where $w(\,(r, \ldots p)\,) < \frac{1}{2} w(C)$ and $w(\,(q, \ldots r)\,) < \frac{1}{2} w(C)$. \\ By lemma~\ref{subpath}, $(r, \ldots p)$ and $(r, \ldots q)$ are shortest paths in both cases $\Box$ \end{quotation}} The partition of the set of relevant cycles is based on theorem~\ref{theoxpq}. For any relevant cycle $C$ including the vertices $r$, $p$, $q$ and eventually $x$, as defined in theorem~\ref{theoxpq}, we define the {\em cycle family\/} associated with $C$ as follows : \Tdefinition{\label{defam}\\% \hspace*{1em} ${\cal F}(C) = \left\{\hbox{$C' \in {\cal C_R}$ $\left| \ \vcenter{\hbox{\em $w(C') = w(C)$ and $C'$ consists of :} \hbox{\begin{minipage}{10cm}\em \poing[1em]{the vertex $r$ and the edge $(p,q)$ (or the path $(p, x, q)$),} \poing[1em]{two shortest paths $(r, \ldots, p)$ and $(r, \ldots, q)$ passing only through vertices smaller than $r$.} \end{minipage}} }\right.$}\right\}$} \begin{center} \vspace*{-1ex} \input{./defamperti2.eepic} \vspace*{-1ex} \end{center} Hence, two cycles $C$ and $C'$ belonging to ${\cal F}(C)$ only differ on the shortest paths from $r$ to $p$ and from $r$ to $q$ that they include. %------Theoreme \Ttheorem{The set of all the relevant cycle families defines a partition of ${\cal C_R}$.} % {\sl\small \begin{quotation} \noindent{\bf Proof } By theorem~\ref{theoxpq} and definition~\ref{defam}, the cycle family associated with a relevant cycle $C$ is unique for a given ordering $\pi$. So any relevant cycle belongs to exactly one family. Then, we define an equivalence relation such that two relevant cycles are equivalent if one belongs to the cycle family of the other $\Box$ \end{quotation}} To describe the family ${\cal F}(C)$, we need a single cycle $C$ which is a {\em prototype\/} of this family. All the other cycles in ${\cal F}(C)$ can be generated from $C$ by replacing paths $(r, \ldots p)$ and $(r, \ldots q)$ with paths of the same weight passing only through vertices smaller than $r$. Hence, a cycle family is properly defined by a triple $r, p, q$ for odd cycles or a quadruple $r, p, q, x$ for even cycles. The number of relevant cycle families depends on the order $\pi$ used to define the families. However, we have the following result : \Ttheorem{the number of relevant cycle families is always polynomial.} % {\sl\small \begin{quotation} \noindent{\bf Proof } The number of families whose prototype is an odd cycle is smaller than $n\,\nu$, since an odd cycle prototype is defined by a vertex $r$ and a cycle closing edge $(p,q)$.\\ As for even cycle families, their prototype is defined by 4 vertices $r, x, p$ and $q$ such that $p$ and $q$ are adjacent to $x$. Hence, the number of even cycle families is smaller than $\sum_{r \in V} \sum_{x \in V,\,\pi(x) \leq \pi(r)} \frac{1}{2}\deg(x)^2\ \leq \ \frac{1}{2}n^2 m$. \\ If the order $\pi$ respects vertex degree ($\forall x \in V,\ \pi(x) \leq \pi(v) \Rightarrow \deg(x) \leq \deg(r)$) there are at most $\sum_{r \in V} \left(\deg(r)\times\sum_{x \in V,\,\pi(x) \leq \pi(r)} \frac{1}{2}\deg(x)\right) \leq 2 m^2$ even cycle families $\Box$ \end{quotation}} \smallskip To compute the union of all the minimum cycle bases, we may find one prototype for each relevant cycle family. %---------------------------============-------------------------------------------------- \section{Computation of cycle prototypes} %---------------------------============-------------------------------------------------- The algorithm we propose to compute cycle prototypes is based on the converse of theorem~\ref{theoxpq}. This converse is not necessarily true but it gives a strong condition on cycle relevance. The outline of the algorithm can be given as follows: \poing{firstly, we compute the set ${\cal C'_I}$ including one cycle for each triple $r, p, q$ (or quadruple $r, p, q, x$) satisfying the condition of theorem~\ref{theoxpq},} \poing{secondly, we use a greedy algorithm to extract relevant cycles from ${\cal C'_I}$.} %------------------------------------------------------ \subsection{Computation of the set ${\cal C'_I}$} %------------------------------------------------------ Before we give a more precise description of the first step of the algorithm, we need to introduce a new definition : \Tdefinition{For any vertex $r$, \\ $V_r = \left\{\ z\in V\ \text{\em such that}\ \left|\ \parbox{9.5cm}{\small there is a shortest path in $G$ from $r$ to $z$ that passes only through vertices which precede $r$ in the ordering $\pi$.}\right. \right\}$} \newcommand{\fath}{\ensuremath{{\cal S}}\xspace} \medskip Then, we can give the outline of the algorithm that computes ${\cal C'_I}$: \setlength{\largeuralgo}{0.8em} \begin{algorithmeg}{19} \noindent\textsf{[Algorithm 1]}\\ \ngba {\sf For} all $r \in V$ {\sf do}:\\ \ngla Compute $V_r$ and $\forall t \in V_r$ find a shortest path $P(r,t)$ from $r$ to $t$;\\ \ngba {\sf For} all $y \in V_r$ {\sf do}:\\ \ngla $\fath\leftarrow \emptyset$;\\ \ngba {\sf For} all $z\in V_r$ such that $z$ is adjacent to $y$ {\sf do}:\\ \ngba {\sf If} $d(r,z) + w(\,(z,y)\,) = d(r,y)$ {\sf Then} \\ \ngla $\fath\leftarrow \fath\,\cup\,\{z\}$;\ \ \ $\star$ {\sl\small $z$ belongs to a shortest path from $r$ to $y$} $\star$\\ \fba \ngba {\sf Else} {\sf If} %\raisebox{0.5ex} {$\left( \hbox{\ \begin{minipage}{8cm}%\small $d(r,z) \neq d(r,y) + w(\,(z,y)\,)$ {\sf and} $\pi(z) < \pi(y)$ \\*[0.3em] \hspace*{3em}{\sf and} $P(r,y)\,\cap\,P(r,z) = \{r\}$\end{minipage}}\right)$} {\sf Then}\\ \ngla Add to ${\cal C'_I}$ the odd cycle $C = P(r,y) + P(r,z) + (z,y)$;\\ \fba\ngla {\sf\footnotesize EndIf}\\ \fba\ngla {\sf\footnotesize EndFor}\\ \ngba {\sf For} any pair of vertices $p, q$ in $\fath$ such that $P(r,p)\,\cap\,P(r,q) = \{r\}$ {\sf Do:} \\ \ngla {\sl Add to } ${\cal C'_I}$ {\sl the even cycle} $C = P(r,p) + P(r,q) + (p, y, q)$;\\ \fba\ngla {\sf\footnotesize EndFor}\\ \fba\ngla {\sf\footnotesize EndFor}\\ \fba\ngla {\sf\footnotesize EndFor} \end{algorithmeg} For a given vertex $r$, the set $V_r$ can be computed at line~2 using a shortest path algorithm. For example, the algorithm presented in \cite{dijk59} can be easily updated to compute $V_r$ by preferably choosing the shortest paths which pass only through vertices smaller than $r$. This variant does not change the algorithm complexity. It remains in $O(n^2)$ operations when the priority queue is implemented as an array, $O(m \log n)$ using a binary heap or $O(m + n\log n)$ with a Fibonacci heap. To generate the prototypes associated with a vertex $r$, we explore any vertex $y$ in $V_r$. We are now going to detail the generation of ${\cal C'_I}$ illustrated by Figure~\ref{algoCI2}. \begin{figure}[htb] \begin{center} \input{algoCI2-2.eepic} \end{center} \vspace*{-2.5em} \caption{Generation of ${\cal C'_I}$.\label{algoCI2}} \end{figure} First, we compute the set $\fath = \{\,z\in \Gamma(y)\,\cap\,V_r~|~d(r,z) + w((z,y)) = d(r,y)\,\}$. So, at the end of line~11, $\fath$ includes all the vertices in $V_r$ adjacent to $y$ such that there is a shortest path from $r$ to $y$ passing through the edge $(z,y)$. For any pair of vertices $p,q$ in $\fath$, we create the even cycle $C = P(r,p) + P(r,q) + (p, y, q)$ when paths $P(r,p)$ and $P(r,q)$ are disjoint (see line~13). As for odd cycles, they are created at line~9 for any vertex $z$ in $\Gamma(y)\,\cap\,V_r$ such that $d(r,y) - w(\,(z,y)\,) < d(r,z) < d(r,y) + w(\,(z,y)\,)$. To avoid cycle duplication, we only consider any vertex $z$ such that $\pi(z) < \pi(y)$. \smallskip A quick analysis of algorithm~1 gives for each vertex $r$ in $V$: \medskip \centerline{\hbox{\begin{minipage}{0.95\linewidth} \poing{line~2 takes $O(m + n\log n)$ operations,} \smallskip \poing{for lines 5 to 11, the critical step is line~8 which takes\\ $\sum_{y\in V_r} O(\deg(y)) \times O(n) \ = \ O(n\,m)$ operations, where $O(n)$ is necessary to check if the paths are disjoint,} \smallskip \poing{line~12-14 takes $\sum_{y\in V_r} O(\deg(y))^2\times O(n)\ \leq \ O(m\,n\,\deg(r))$ if we suppose that the order $\pi$ respects the vertex degree (i.e. $\forall y\in V_r,\ \deg(y) \leq \deg(r)$).} \end{minipage}}} \medskip So, algorithm~1 takes {\boldmath $O(n\,m^2)$} operations. \smallskip \Tlemma{\label{tailleCI}If order $\pi$ satisfies $\forall x, y \in V,\ \ \pi(x) \leq \pi(y) \Rightarrow \deg(x) \leq \deg(y)$\\ then the cardinality of set ${\cal C^{'}_I}$ is lower than $(2 m^2 + \nu n)$. } {\sl \small\begin{quotation} \noindent{\bf Proof } The number of {\em odd\/} cycles in ${\cal C^{'}_I}$ is less than $\nu n$. As for the {\em even\/} cycles, they are at most $\sum_{r \in V} \sum_{y \in V_r} \frac{1}{2}\deg(y)^2$. For any $y$ in $V_r,\ \deg(y) \leq \deg(r)$. So, there are at most $\sum_{r \in V} \left(\deg(r)\times\sum_{y \in V_r} \frac{1}{2}\deg(y)\right) \leq 2 m^2$ even cycles in ${\cal C^{'}_I}$~$\Box$ \end{quotation}} \smallskip \Ttheorem{\label{CI2complet} ${\cal C^{'}_I}$ includes one and only one prototype of each relevant cycle family.} {\sl \small\begin{quotation} \noindent{\bf Proof } Let $C=(r,\ldots ,p,x,q,\ldots, r)$ be a relevant even cycle (if $C$ is odd, the proof is quite similar). Assume that $r$ is the greatest vertex in $C$ according to $\pi$ and $x$ is the unique vertex in $C$ such that $d(r,x) = \frac{1}{2} w(C)$.\\ Now consider the exploration of vertex $y = x$ in algorithm~1. By theorem~\ref{theoxpq}, $(r,\ldots ,p)$ and $(r, \ldots ,q)$ are shortest paths. So $p$ and $q$ belong to ${\cal S}$. Define $C'$ to be the cycle added to ${\cal C'_I}$ at line~13 for the pair of vertices $p, q$. By construction of ${\cal C'_I}$, $C'$ is unique.\\ Cycles $C$ and $C'$ only differ by the shortest paths $(r,\ldots ,p)$ and $(r,\ldots ,q)$ that they include. The sum $C + C'$ defines a set of cycles which are smaller than $C$. Hence, cycle $C'$ must be relevant since $C$ is relevant. So, $C'$ is the unique prototype of ${\cal F}(C)$ which belongs to ${\cal C^{'}_I}$ $\Box$ \end{quotation}} %------------------------------------------------------ \subsection{Computation of a set of prototypes} %------------------------------------------------------ By theorem~\ref{CI2complet}, ${\cal C_R}\,\cap\,{\cal C^{'}_I}$ is a set of prototypes. So, we have to extract all the relevant cycles in ${\cal C^{'}_I}$. As in Horton's algorithm, a minimum cycle basis ${\cal B}$ is calculated by processing the cycles of ${\cal C^{'}_I}$ in order of their weight. During the processing of a cycle $C$, we denote by ${\cal B}_{<}$ and ${\cal B}_{=}$ the subsets of cycles in the current sub-basis whose weights are less than $w(C)$ and equal to $w(C)$, respectively. By Lemma~\ref{defperti2}, $C$ is relevant when the set ${\cal B}_{<}\,\cup\,\{C\}$ is independent. When this check succeeds, cycle $C$ is added to ${\cal B}_{=}$ if the set ${\cal B}_{<}\,\cup\,\{C\}\,\cup\,{\cal B}_{=}$ is also independent. The processing stops when ${\cal B}$ is complete and all the cycles having the same weight as the greatest one in ${\cal B}$ have been tested. The current minimal sub-basis of ${\cal B}$ is represented by a $(|{\cal B}_{<}| + |{\cal B}_{=}|) \times m$ boolean matrix. To test if set ${\cal B}_{<}\,\cup\,\{C\}$ is independent, we perform a Gaussian elimination on the first rows of the matrix which are associated with ${\cal B}_{<}$. When this check succeeds, the Gaussian elimination follows on the other rows to test if set ${\cal B}_{<}\,\cup\,{\cal B}_{=}\,\cup\,\{C\}$ is also independent. Since ${\cal B}$ contains at most $\nu$ cycles, each check of a cycle is performed in $O(\nu m)$. By lemma~\ref{tailleCI}, the cardinality of ${\cal C'_I}$ is in $O(m^2)$. So, the set of prototypes ${\cal C'_I}\,\cap\,{\cal C_R}$ can be generated in {\boldmath $O({\nu}\,m^3)$} operations. %---------------------------============-------------------------------------------------- \section{Enumeration of ${\cal C_R}$} %---------------------------============-------------------------------------------------- ${\cal C_R}$ is completely described by a set of prototypes of the families defined in section~\ref{defpartfam}. From this set of prototypes, the union of all the minimum cycle bases can easily be listed. Consider a cycle prototype $C \in {\cal C_R}\,\cap\,{\cal C^{'}_{I}}$. To generate the cycle family ${\cal F}(C)$, we define a directed graph $D_r = (V_r,U_r)$ associated with the vertex $r$ such that: \[ U_r = \left\{\text{\sl directed edge $(y,z)$ such that } \left|\ \parbox{8cm}{\small $(z,y)$ belongs to a shortest path in $G$ from $r$ to $y$ that passes only through vertices which precede $r$ in the ordering $\pi$.}\right. \right\}\] \medskip \begin{center} \vspace*{-1ex} \input{./digraph-perti.eepic} \vspace*{-1ex} \end{center} \bigskip The computation of the digraph $D_r$ can be performed directly in algorithm~1. For each directed edge $(y,z)$ in $U_r$, $z$ belongs to the set $\fath$ which is computed at line~7 of the algorithm. The digraph $D_r$ has two major properties: \smallskip \raisebox{0.2ex}{${\scriptscriptstyle\bullet}$}\ It has no directed cycle, \smallskip \raisebox{0.2ex}{${\scriptscriptstyle\bullet}$}\ $\forall x \in V_r$, any directed path $(x, \ldots , r)$ in $D_r$ corresponds to a shortest path in $G$. \medskip \noindent To list all the paths from $x$ to $r$ in $D_r$, we use a backtracking function which is based on a deep first search from $x$. This recursive function can be resumed as follows: \medskip \setlength{\largeuralgo}{0.5em} \begin{algorithme} \noindent \sba\textsf{Function List\_Paths( $x$; {\it current\_path} )}\\ \sla add $x$ at the head-end of {\it current\_path};\\ \sla \textsf{If} $x = r$ \textsf{Then Return($\{ \mbox{\it current\_path}\}$)}\\ \sba \textsf{Else:}\\ \sla $\mbox{\it Result}\leftarrow \emptyset$;\\ \sba \textsf{For} any $z$ such that $(x, z) \in U_r$ \textsf{Do}\\ \sla\traitfba $\mbox{\it Result}\leftarrow \mbox{\it Result}\;\cup\;$\textsf{List\_Paths($z$, {\it current\_path})};\fba\\ \sla\trait2fba \textsf{Return(\mbox{\it Result})} \end{algorithme} \smallskip To compute ${\cal F}(C)$, we first replace the path $(p, \ldots ,r)$ in $C$ by each one of the paths returned by the call \textsf{List\_Paths($p$, $\emptyset$)}. Then, in any cycle generated this way, we replace the path $(q, \ldots ,r)$ by each one of the paths resulting from %the call \textsf{List\_Paths($q$,~$\emptyset$)}. Each cycle in ${\cal F}(C)$ corresponds to a pair of paths $(p, \ldots ,r)$, $(q, \ldots ,r)$. Since the computation of each path takes a number of operations in order of the path cardinality, the family ${\cal F}(C)$ can be listed in $O(\, n\, |{\cal F}(C)|\,)$. So, the generation of ${\cal C_R}$ from subset ${\cal C_R}\,\cap\,{\cal C^{'}_{I}}$ is performed in $O(n\,|{\cal C_R}|)$ operations (including cycle enumeration). Note that the use of prototypes substantially optimizes the generation of ${\cal C_R}$: if a cycle prototype is relevant, this implies that all cycles of the corresponding family are relevant. Therefore, the number of cycle relevance checks is polynomial since it is in $O(|{\cal C^{'}_{I}}|)$ instead of $O(|{\cal C_R}|)$. %======================================================================================== %======================================================================================== \section{Computation of the number of relevant cycles} %======================================================================================== %-------------------------------------------- \subsection{Size of ${\cal C_R}$}\label{sizefam} %-------------------------------------------- Using cycle families to describe ${\cal C_R}$ provides a polynomial time algorithm to compute the size of this set without generating all cycles. This is particularly interesting for real-world problems to determine whether the number of relevant cycles is polynomial or not. To perform this computation we may evaluate the number of shortest paths from $r$ to any vertex $x$, which passe only throught vertices in $V_r$. This number is denoted by $\psi_r (x)$. Of course, $\psi_r (r) = 1$. In algorithm~1, we compute, for each vertex $y$ in $V_r$, the set ${\cal S}$ of all the vertices $z$ in $V_r$ such that there is a shortest path from $r$ to $y$ which ends in the edge $(z, y)$. \smallskip Then, one can easily prove that: {$\displaystyle \forall y \in V_r,\ \ \psi_r (y) = \sum_{z \in\,{\cal S}}\!\!\psi_r(z)$} \smallskip This result gives an efficient method to compute the function $\psi_r$ if the vertices in $V_r$ are processed according to a {\em topological sort\/}\footnote{In a graph without directed cycles, a topological sort is an ordering on the vertices such that : if there is a directed edge from $x$ to $y$ then $x$ is greater than $y$.} of the graph $D_r$. Denote by $C^{r}_{p,q}$ a cycle created from vertices $r$, $p$ and $q$ (and eventually $x$) according to the previous notations. If $C^{r}_{p,q}$ belongs to ${\cal C_R}\,\cap\,{\cal C^{'}_{I}}$, then the number of relevant cycles in family ${\cal F}(C^{r}_{p,q})$ is equal to $\psi_r(p)\times\psi_r(q)$ (see Figure~\ref{numberperti}). Consequently, \[ |{\cal C_R}| = \sum_{C^{r}_{p,q}\,\in\,{\cal C_R}\,\cap\,{\cal C^{'}_{I}}} \psi_r(p)\times\psi_r(q)\] \begin{figure} \begin{center} \vspace*{-1.5em} %-3 \input{figures/numberperti.eepic} \vspace*{-2em} \end{center} \caption{\label{numberperti} Since $\psi_r(p)=4$ and $\psi_r(q)=6$, cycle family ${\cal F}(C^{r}_{p,q})$ (corresponding to cycle $C^{r}_{p,q}$ in solid lines), contains $24$ relevant cycles. } \end{figure} %------------------------------------------------------------------------------------------- \subsection{Number of relevant cycles including a given vertex}\label{NumberFam} %------------------------------------------------------------------------------------------- Determination of the union of all the minimum cycle bases as a polynomial number of cycle prototypes has still another interest. It provides a way of calculating, in polynomial time, the number of relevant cycles of a given weight which include each vertex. For example, in Figure~\ref{numberperti}, vertex $a$ belongs to two 4-edge relevant cycles, one 6-edge cycle and twelve 13-edge ones. This knowledge can be useful to distinguish vertices according to their membership to more or less complex cyclic structures. For example, in organic chemistry this can help for taxonomy purposes in the determination of nomenclature names. Let us consider a cycle family ${\cal F}(C^{r}_{p,q})$. % whose prototype is cycle $C^{r}_{p,q}$. Denote by $\#in(y,{\cal F}(C^{r}_{p,q}))$ the number of cycles in ${\cal F}(C^{r}_{p,q})$ which include vertex $y$. Assume that vertex $y$ belongs to path $(r,..,q)$. Define $\phi_r(y,q)$ to be the number of shortest paths from $y$ to $q$ which are included in $D_r$. For example, in Figure~\ref{numberperti}, $\phi_r(y,q) = 3$. We can determine $\phi_r(y,q)$ using a topological sort, in the same way as for the determination of $\psi_r$. This search needs $O(m)$ operations. Since there are at most $O(m^2)$ families, the global complexity is $O(m^3)$. Then, one can easily prove the following result: \[\#in(y,{\cal F}(C^{r}_{p,q})) = \psi_r(y) \times \phi_r(y,q) \times \psi_r(p) \] In Figure~\ref{numberperti}, for vertex $y$, $\ \#in(y,{\cal F}(C^{r}_{p,q})) = 2 \times 3 \times 4 = 24 $. %======================================================================================== %======================================================================================== \section*{Conclusion} %======================================================================================== This paper deals with the computation of the {\em union of all the minimum cycle bases\/} of a graph. We present the first efficient algorithm to find this set of cycles. We call the {\em union of all the minimum cycle bases\/} the {\em set of relevant cycles\/} and denote it by ${\cal C_R}$. It is the smallest generating set of the cycle space which is unique for a given graph. We propose a polynomial time algorithm to compute ${\cal C_R}$ as a set of cycle families. Each family is represented by a cycle prototype and all the families constitute a partition of ${\cal C_R}$. From the set of prototypes, all the relevant cycles can be listed in $O(n|{\cal C_R}|)$ time (including output). We also propose a polynomial method to determine the number of relevant cycles which include a given vertex. The use of prototypes provides an efficient compact representation of the union of all the minimum cycle bases. For real-world applications, the enumeration of ${\cal C_R}$ is generally unnecessary. One can envisage two major improvements for the problem of the union of all the minimum cycle bases. Firstly, it would be interesting to find an ordering on the vertices such that the number of relevant cycle families is minimum. Secondly, the algorithm we propose is polynomial but it can probably be improved. The critical step is the extraction of relevant cycles from the initial set ${\cal C'_I}$. If a strong condition were found for characterizing relevant cycles without a check for independence, the improvement could be very significant. This is also true in the case of Horton's algorithm to compute a minimum cycle basis. It seems to be that an improvement to Horton's algorithm would entail an improvement to the one proposed here. An other open problem is the enumeration of all the minimum cycle bases of a graph. It would be interesting to find a polynomial way to represent all these bases. But this problem has probably no real application. Conversely, the notion of relevant cycles can be applied to real-world problems. The union of all the minimum cycle bases has been successfully used in the system RESYN \cite{vism92,vism95b}, a program for the planning of complex organic syntheses, to evaluate the set of chemically relevant cycles in a molecule. %======================================================================================== \end{document}