Interchangeability of Relevant Cycles in Graphs

Petra M. Gleiss^{a}, Josef Leydold^{b,∗} and Peter F. Stadler^{a,c}

aInstitute for Theoretical Chemistry and Molecular Structural Biology, University of Vienna, Währingerstrasse 17, A-1090 Vienna, Austria Phone: **43 1 4277-52737 Fax: **43 1 4277-52793

             E-Mail: {pmg,studla}@tbi.univie.ac.at
         URL: http://www.tbi.univie.ac.at/~{pmg,studla}

bDept. for Applied Statistics and Data Processing University of Economics and Business Administration Augasse 2-6, A-1090 Wien, Austria Phone: **43 1 31336-4695 Fax: **43 1 31336-738

          E-Mail: Josef.Leydold@statistik.wu-wien.ac.at
        URL: http://statistik.wu-wien.ac.at/staff/leydold

∗Address for correspondence

cThe Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, NM 87501, USA

Phone: (505) 984 8800 Fax: (505) 982 0565

                  E-Mail: stadler@santafe.edu
            URL: http://www.tbi.univie.ac.at/~studla

Submitted: July 26, 1999; Accepted: March 12, 2000.

Abstract The set R of relevant cycles of a graph G is the union of its minimum cycle

bases. We introduce a partition of R such that each cycle in a class W can be expressed as a sum of other cycles in W and shorter cycles. It is shown that each minimum cycle basis contains the same number of representatives of a given class W. This result is used to derive upper and lower bounds on the number of distinct minimum cycle bases. Finally, we give a polynomial-time algorithm to compute this partition.

Keywords: Minimum Cycle Basis, Relevant Cycles

AMS Subject Classification: Primary 05C38. Secondary 05C85, 92D20, 92E10.

1. Introduction

Cycle bases of graphs have a variety of applications in science and engineering. For example, applications occur in structural flexibility analysis [9], electrical networks [3], and in chemical structure storage and retrieval systems [5]. Brief surveys and extensive references can be found in [8, 7].

The set R of relevant cycles of a graph G is the union of its minimum cycle bases [12, 15]. We define an equivalence relation “interchangeability” on R such that the cycles in a class W ∈ 𝔓 of the associated partition 𝔓 can be expressed as a sum of a linearly independent set consisting of other cycles in W and shorter cycles. The motivation for introducing 𝔓 originated in the context of RNA folding; a brief sketch is included as appendix.

The main result is that every class W in 𝔓 has the following property: the cardinality of the intersection of W with every minimal cycle basis is the same. This result is used to prove upper and lower bounds on the number of distinct minimal cycle bases.

The partition 𝔓 can be obtained in polynomial time from R. While the number of relevant cycles may grow exponentially with the number |V | of vertices [15], there are typically only O(|V |^{3}) relevant cycles [6].

2. Preliminaries

Let G(V, E) be a simple, connected, unweighted, undirected graph with vertex set V and edge set E. The set E of all subsets of E forms an m-dimensional vector space over GF(2) with vector addition X ⊕Y := (X ∪Y)\(X ∩Y) and scalar multiplication 1 · X = X, 0 · X = ∅ for all X, Y ∈ E. In order to simplify the notation we shall write

⨁_{X} = ⨁_{C∈X} C  (1)

for X ⊆ E. A generalized cycle is a subgraph such that any vertex degree is even. A cycle is a connected subgraph such that every vertex has degree 2. We represent a (generalized) cycle by its edge set C.

The set C of all generalized cycles forms a subspace of (E, ⊕, ·) which is called the cycle space of G. A basis B of the cycle space C is called a cycle basis of G(V, E) [1]. The dimension of the cycle space is the cyclomatic number or first Betti number ν(G) = |E| − |V | + 1. It is obvious that the cycle space of a graph is the direct sum of the cycle spaces of its 2-connected components. It will be sufficient therefore to consider only 2-connected graphs in this contribution.

The length |C| of a generalized cycle C is the number of its edges. The length ℓ(B) of a cycle basis B is the sum of the lengths of its generalized cycles: ℓ(B) = ∑_{C∈B} |C|. A minimum cycle basis M is a cycle basis with minimum length. The generalized cycles in M are chord-less cycles (see [8]). Hence we may consider cycles instead of generalized cycles from here on. For the sake of completeness we note that a minimum cycle basis is a cycle basis in which the longest cycle has the minimum possible length [2].

Definition 1. [12] A cycle C is relevant if it cannot be represented as an ⊕-sum of shorter cycles. We denote the set of all relevant cycles by R.

Proposition 2. [15] A cycle C is relevant if and only if it is contained in a minimum cycle basis.

Definition 3. [6] A cycle C in G is essential if it is contained in every minimum cycle basis of G.

The set of all cycles of a graph G forms a matroid, see e.g. [11, 18]. We restate this fact in the following form:

Proposition 4 (Matroid Property). Let Q be a set of cycles containing a minimum cycle basis. Then a minimum cycle basis B can be extracted from Q by a greedy procedure in the following way: (i) Sort Q by cycle length and set B = ∅. (ii) Transversing Q in the established order, set B ← B ∪ {C} whenever B ∪ {C} is linearly independent.

3. A Partition of R

Lemma 5. For each relevant cycle C ∈ R, exactly one of the following holds:

(i) C is essential, or

(ii) There is a cycle C′ ∈ R, C′ ≠ C, and a set of relevant cycles X ⊆ R \ {C, C′} such that X ∪{C′} is linearly independent, |C| = |C′|, |C′′| ≤ |C| for all C′′ ∈ X, and C = C′ ⊕ ⨁_{X}.

Proof. Let Y = {C′′ ∈ R| |C′′| ≤ |C|}. If rank (Y) > rank (Y \ {C}) , then C is contained in every minimum cycle basis as an immediate consequence of the matroid property. In other words, C is essential.

Now assume rank (Y) = rank (Y \ {C}) . Hence C = ⨁_{Z} for some Z ⊆ Y \ {C}. Without loss of generality we may assume that Z is an independent set of cycles. By the relevance of C, Z cannot consist only of cycles that are all strictly shorter than C, thus there is C′ ∈ Z such that |C′| = |C|, and we can write

C = C′ ⊕ ⨁_{Z\{C′}}.  (2)

It remains to show that C is not essential in this case: Adding C ⊕ C′ to both sides of equ.(2) yields C′ = C ⊕ ⨁_{Z\{C′}}. Thus we may extract two different minimum cycle bases from R one of which contains C but not C′, while the other contains C′ but not C, simply by ranking C before or after C′ when sorting R. Thus neither C nor C′ is essential.

Definition 6. Two relevant cycles C, C′ ∈ R are interchangeable, C ↔ C′, if (i) |C| = |C′| and (ii) there is a set X ⊂ R, C, C′ ∉ X, X ∪{C′} is a linearly independent subset of relevant cycles, such that C = C′ ⊕ ⨁_{X} and |C′′| ≤ |C| for all C′′ ∈ X.

Lemma 7. Interchangeability is an equivalence relation on R.

Proof. Trivially, we have C ↔ C; symmetry follows immediately from the proof of lemma 5. In order to verify transitivity, assume C ↔ C′, C′ ↔ C′′ and set C′ = C ⊕ ⨁_{X} and C′′ = C′ ⊕ ⨁_{X′}. We have to distinguish two cases:

(i) C′′ ∈ X. Then C′ = C ⊕ C′′ ⊕ ⨁_{X \{C′′}}. Adding C ⊕ C′ on both sides yields C = C′′ ⊕ ⨁_{X \{C′′}∪{C′}}. By assumption, X ∪ {C′} does not contain C and is an independent subset of relevant cycles, i.e., C ↔ C′′. The case C ∈ X′ is treated analogously.

(ii) C′′ ∉ X and C ∉ X′. We have

C′′ = (C ⊕ ⨁_{X} ) ⊕ ⨁_{X′} = C ⊕ ⨁_{X △X′} = C ⊕ ⨁_{Z}

where X △X′ denotes the symmetric difference, and Z ⊆ X △X′ is a non-empty independent set of cycles that does not contain C or C′′. Thus C′′ ↔ C.

Corollary 8. A relevant cycle C is essential if and only if it is not ↔-interchangeable with any other cycle.

Remark. We cannot assume that for the set X ⊂ R in definition 6, X ∪ {C′} is a subset of a minimum cycle basis. Figure 1 gives a counter example. In what follows let C_{F}, C′_{F}, C_{G} and C′_{G} denote the relevant cycles of length 6 through F and G, respectively, and let C_{O} be the cycle {O_{1}, …, O_{6}}. Z always denotes an independent subset of R \ {C_{F} , C′_{F} , C_{G}, C′_{F} , C_{O}}. Then C_{F} = C_{G} ⊕ (C′_{G} ⊕ C′_{F} ⊕ ⨁_{Z}), where the right hand side is linearly independent, i.e., C_{F} ↔ C_{G}. However, the r.h.s. contains both C_{G} and C′_{G} and hence it is not a subset of a minimum cycle basis. Moreover, C_{F} cannot be expressed as an ⊕-sum of an independent subset of relevant cycles that contains C_{G} but not C′_{G}.

The graph in figure 1 demonstrates also that we cannot define a “stronger” interchangeability relation, ↔_{s}, by replacing the condition that X ∪ {C′} is independent by “X ∪{C′} is a subset of a minimum cycle basis” in definition 6. The relation ↔_{s} is not symmetric: We find C_{F} = C_{O} ⊕ (C′_{F} ⊕ ⨁_{Z}), where the r.h.s. is a subset of a minimum cycle basis, i.e., C_{F} ↔_{s} C_{O}. However, we always have C_{O} = C_{F} ⊕ (C′_{F} ⊕ ⨁_{Z}) where the r.h.s is not a subset of a minimum cycle basis.

O_{1}  O_{2}O_{3} O_{4} O_{5}O_{6}  F G

Figure 1. The set of relevant cycles of this graph consists of all triangles, all 4-cycles, two 6-cycles through F, two 6-cycles through G and the seven 6-cycles through at least one of the edges O_{i}. The three inner hexagons (thick lines) are not relevant, because they are the sum of triangles and 4-cycles. Notice that all 3- and 4-cycles are essential. Moreover, every minimum cycle basis contains exactly one 6-cycle through F and G, respectively, and six of the seven 6-cycles through at least one of the edges O_{i}. Moreover, no 6-cycle is essential.

Lemma 9. Let C be a relevant cycle such that C = ⨁_{X} for a linearly independent set X of cycles with length less or equal |C|. Set X_{=} = {C′ ∈ X ||C′| = |C|}. Then C′ ↔ C for each cycle C′ ∈ X_{=}.

Proof. By lemma 7 C ↔ C. Assume there exists a C′ ∈ X_{=} \ {C}. Then C′ = C ⊕ ⨁_{X_{=}\{C}}, i.e., C′ ↔ C as proposed.

Lemma 10. Let B be a minimum cycle basis and let W be an ↔-equivalence class of R. Then B ∩ W ≠ ∅.

Proof. Suppose there is a minimum cycle basis B and an ↔-equivalence class W such that W ∩ B = ∅. Choose C ∈ W. By the matroid property there is an independent set of cycles Q = Q_{=} ∪ Q_{<} ⊆ B such that C = ⨁_{Q}. By lemma 9 we have Q_{=} ⊆ W which contradicts B ∩ W = ∅ unless Q_{=} = ∅. Thus C = ⨁_{Q_{<}} and hence C ∉ B by proposition 2.

Theorem 11. Let B and B′ be two minimum cycle bases and let W be an ↔- equivalence class of R. Then |B ∩ W| = |B′ ∩ W|.

Proof. Consider an ↔-equivalence class W consisting of cycles of length l. Define B_{=} = {C ∈ B||C| = l}, B_{<} = {C ∈ B||C| < l}, and analogously for the second basis B′. Assume |B′ ∩ W| > |B ∩ W| and set W ∩ B = {C_{1}, …, C_{j}}, W ∩ B′ = {D_{1}, …, D_{j}, …, D_{k}}. By lemma 10, j > 0. As a consequence of the matroid property we may assume B′_{<} = B_{<} and we may write each D_{i} as a linear combination of cycles from B_{<} ∪ B_{=}. Moreover by lemma 9 this linear combination cannot contain any cycles from B_{=} \W. Since there are more than j cycles D_{i} there is a non-trivial linear combination

F = ⨁_{i∈I} D_{i} = [⨁_{i∈J} C_{i}] ⊕ ⨁_{X ⊆B′_{<}}

with I ⊆ {1, …, k} and J ⊆ {1, …, j} such that ⨁_{i∈J} C_{i} = 0. Thus

[⨁_{i∈I} D_{i}] ⊕ ⨁_{X ⊆B′_{<}} = 0

and hence {D_{i}| ∈ I} ∪ X ⊆ B′_{=} ∪ B′_{<} is linearly dependent, contradicting the assumption that B′ is a basis.

As an immediate consequence of theorem 11 we recover the well known fact [2, Thm. 3], that any two minimum cycle bases contain the same number of cycles with given length.

Definition 12. Let B be a minimum cycle basis and let W be an ↔-equivalence class of R. We call knar (W) = |B ∩ W| the relative rank of W in R.

Corollary 13. Let W be an ↔-equivalence class such that knar (W) = k. Then each C ∈ W can be written as C = ⨁_{Y} ⊕ ⨁_{Z} where Z consists only of cycles shorter than |C| and Y ⊆ W \ {C} has cardinality |Y| ≤ knar (W) .

We close this section with a few examples: Complete graphs. The relevant cycles of a K_{n}, n ≥ 3, are its triangles. It follows immediately that all triangles are ↔-equivalent. Outerplanar graphs. Outerplanar graphs have a unique minimal cycle basis [10], i.e., each relevant cycle is essential. Thus there are ν(G) interchangeability classes consisting of a single cycle. Triangulations. For each triangulation of the sphere all relevant cycles of the corresponding graph are triangles. Moreover, The ⊕-sum of all triangles equals 0, while any proper subset is independent. Thus there is a single ↔-equivalence class with knar (W) = |R| − 1.

If we change the situation a little bit, such that there is exactly one face cycle C of length l > 3, i.e., the graphs corresponds to a triangulation of the plane but not the sphere, then C is the ⊕-sum of all triangles and hence not relevant. Thus all triangles are essential, i.e., we have |R| ↔-equivalence classes, all of knar (W) = 1. This example demonstrates that partitioning into ↔-equivalence classes — similar to number and length of minimum cycle bases — can be very unstable against small changes in the geometry of graphs. Chordal graphs. The next example shows that there are rather “irregular-looking” examples for which all relevant cycles are contained in the same ↔-equivalence class. A graph is chordal (also called triangulated or rigid circuit) if all cycles of length |C| ≥ 4 contain a chord, i.e., an edge connecting two of its non-adjacent vertices.

Let G be connected and let A be a minimal separating vertex set. Then there are two connected graphs G_{i} = (V_{i}, E_{i}), i = 1, 2 such that V = V_{1} ∪ V_{2}, E = E_{1} ∪ E_{2}, and A = V_{1} ∩ V_{2}. If Σ = (A, E_{1} ∩ E_{2}) is a complete graph, G_{1} ∪ G_{2} is called a simplicial decomposition of G at A. This procedure can be repeated until no further separating complete graphs can be found. It can be shown that the resulting indecomposable subgraphs are independent of the order of the decomposition [14, Prop.4.1]. The resulting components are the simplicial summands of G. A graph is chordal if and only if all its simplicial summands are complete graphs [4].

Lemma 14. If G is a 3-connected chordal graph then R consists of a single ↔- equivalence class.

Proof. Since C ∈ R only if it is chord-less, it follows that all relevant cycles of a chordal graph are triangles. If G is 3-connected, the minimum separating clique Σ contains a triangle. Let G_{1} and G_{2} be the two adjacent simplicial summands. Then all triangles in G_{1} are contained in a single ↔-equivalence class; the same is true for all triangles in G_{2}. Since the intersection of G_{1} and G_{2} contains at least one triangle by assumption, all triangles of their union are contained in the same ↔-equivalence class, and the lemma follows by induction.

4. The Number of Minimal Cycle Bases

As an application of the ↔-partition of R we derive bounds on the number of distinct minimal cycle bases of G.

Theorem 15. Let R = ⋃_{i=1}^{m} W_{i} be the partition of the set of relevant cycles into ↔-equivalence classes. Then the number M of distinct minimum cycle bases satisfies

∏_{i=1}^{m} |W_{i}| ≤ M ≤ ∏_{i=1}^{m} \binom{|W_{i}|}{knar (W_{i})}.  (3)

Proof. The lower bound follows from the fact that, by lemma 10, each minimum cycle basis contains at least one element from each ↔-equivalence class, and the fact that, by the matroid property, each element of W_{i} can be chosen. The upper bound follows directly from theorem 11 by assuming that the knar (W_{i}) basis elements from W_{i} can be chosen freely.

There even exists a universal bound that depends only on the number of relevant cycles and the cyclomatic number.

Corollary 16. The number M of distinct minimum cycle bases satisfies

M ≤ \binom{|R|}{ν(G)}.  (4)

Proof. This upper bound follows immediately if we neglect any restrictions for the choice of ν(G) relevant cycles for a minimum cycle basis.

Corollary 17. Upper and lower bound coincide in equ.(3) if all ↔-equivalence classes satisfy knar (W) = 1 or knar (W) = |W| − 1.

It is tempting to speculate that the upper bound might be attained by all graphs. Equivalently, then we could choose knar (W) cycles from W without restrictions when extracting a minimum cycle basis from R. Unfortunately, this is not the case as the following examples show. The triangles of K_{5}. Figure 2 lists the 10 triangles of K_{5}. Each triangle is contained in two of the five induced K_{4}-subgraphs a to e. Thus there are 5 dependent four-sets of cycles:

\begin{matrix}A ⊕ B ⊕ G ⊕ J = 0 & B ⊕ C ⊕ F ⊕ H = 0 & A ⊕ E ⊕ F ⊕ I = 0 \\ C ⊕ D ⊕ G ⊕ I = 0 & D ⊕ E ⊕ H ⊕ J = 0 \end{matrix}

It is clear that all 10 cycles A through J are ↔-equivalent forming a single equivalence class with knar (triangles) = ν(K_{5}) = 6. In general, it is clear that all triangles of a complete graph K_{n}, n ≥ 3, belong to a single ↔-equivalence class.

More importantly, however, 5 of the \binom{10}{4} = 210 combinations of 4 cycles and hence at least 5 \binom{6}{2} = 75 of the \binom{10}{6} = 210 sets of six triangles are dependent. As a consequence, neither the upper nor the lower bound in equ.(3) is an equality for K_{5}.

1  2  3 4 56  7  89 10

1 2 3 4 5 6 7 8 9 10 a b c d e
A * *  *  * *
B  * *  *  *  *
C  * *  *  * *
D  * *  *  * *
E *  *  *  * *
F  *  *  *  *  *
G  *  *  *  *  *
H  *  *  *  * *
I  * * *  * *
J *  * *  * *

Figure 2. The 10 triangles of K_{5} cover the five sub-K_{4}s a through e twice.

Small relative ranks. The final example shows that Corollary 17 cannot be improved even if we restrict ourselves to graphs in which all ↔-classes have small relative rank, or when only a single ↔-class has knar (W) ≥ 1. The family of graphs in figure 3 shows that linearly dependent subsets V ⊂ W with |V| ≤ knar (W) can be found even for knar (W) = 2.

v_{1} v_{2} H_{1} H_{2} … H_{n}

Figure 3. The 4-cycles are all essential. All 6-cycles are in one equivalence class W with knar (W) = n+1 and |W| = n^{2}/2+3n/2+2. The outer cycle (of length 6) can be expressed as ⊕-sum of all 4-cycles and the inner 6-cycle that does not contain any path H_{i}. Thus no minimum cycle basis can contain these two 6-cycles.

5. A Connection with Vismara’s Prototypes

Phillipe Vismara [15] describes an algorithm for constructing the set of relevant cycles R that makes use of a partitioning of R into cycle families. Let ⪯ be an arbitrary ordering of the vertex set V of G. Set V_{r} = {x ∈ V, x ⪯ r}.

Proposition 18. [15] Let C be a relevant cycle, and let r be the vertex of C that is maximal w.r.t. the order ⪯. Then there are vertices p, q ∈ V_{r} such that C consists of two disjoint shortest paths (r … p) and (r … q) of the same lengths linked by the edge {p, q} if |C| is odd or a path (p, x, q), x ∈ V_{r}, if |C| is even.

Remark. A subgraph H of G is isometric if d_{H}(x, y) = d_{G}(x, y) for all vertices x, y ∈ V_{H}. It is easy to verify that a relevant cycle must be isometric. The converse is not true, however: Horton [8] gives a counter-example.

Definition 19. [15] Let C_{pqx}^{r} be a cycle as described in proposition 18. The cycle family F_{pqx}^{r} consists of all cycles C satisfying the following conditions:

(i) |C| = |C_{pqx}^{r}|;

(ii) C contains the vertex r as well as the edge {p, q} or the path (p, x, q);

(iii) There are two shortest paths (p … r) and (q … r) in C that pass only through vertices ⪯-smaller than r, i.e., that are contained in V_{r}.

Note that the cycle families F_{pqx}^{r} explicitly depend of the order ⪯ on V. Vismara shows that {F_{pqx}^{r}|C_{pqx}^{r} is relevant} forms a partition of R for any order ⪯ on V.

Lemma 20. Let F ⊆ R be a relevant cycle family, and let B be a minimum cycle basis. Then for all C, C′ ∈ F there is an independent set Y ⊆ B such that C ⊕ C′ = ⨁_{Y} and |C′′| < |C| = |C′| for all C′′ ∈ Y.

Proof. Let P, P′ and Q, Q′ be the paths connecting (r, p) and (r, q) in C and C′, respectively. Then each of the combinations of paths {P, Q}, {P′, Q}, {P, Q′}, {P′, Q′} belongs to a (possibly generalized) cycle in F, which we denote by C = C_{P Q}, C_{P′Q}, C_{P Q′}, and C′ = C_{P′Q′} as outlined in [15]. Explicitly we have C_{P Q} = P ⊕ Q ⊕ {p, q} if |C| is odd and C_{P Q} = P ⊕ Q ⊕ {p, x} ⊕ {x, q} if |C| is odd, etc. Note that the cycles C_{P′Q} and C_{P Q′} are not necessarily connected. Since P and P′ have the same end points, their sum P ⊕ P′ is an edge-disjoint union of cycles, which we denote by A. Thus C = C_{P′Q} ⊕ ⨁_{A} and analogously we obtain C′ = C_{P′Q′} = C_{P′Q} ⊕ ⨁_{A′}, and thus C′ = C ⊕ ⨁_{A△A′}. Since each cycle C′′ ∈ A△A′ satisfies |C′′| ≤ 2d(r, p) = 2d(r, q) < |C|, it follows from the matroid property that C′′ can be written as an ⊕-sum of basis elements taken from Y.

Corollary 21. For each relevant cycle family F there is an ↔-equivalence class W such that F ⊆ W.

6. Computing Interchangeability Classes

Clearly, we may treat each length-class separately, since ↔-equivalent cycles have the same length k. For a given length l we set B_{<} = {C ∈ B||C| < l} = {C_{1}, …, C_{n_{0}}} where B is an arbitrary minimal cycle basis, and R_{=} = {C ∈ R||C| = l} = {C_{n_{0}+1}, …, C_{n_{1}}}. By lemma 9, two cycles C_{j′}, C_{j′′} of length l are ↔-equivalent if and only if the linear equation

( ⨁_{C_{k′}∈B_{<}} a_{k′}C_{k′} ) ⊕ ( ⨁_{C_{k}∈R_{=}} a_{k}C_{k}) = 0  (5)

has a solution with a_{j′} = a_{j′′} = 1 which is minimal in the following sense: if we take any strict subset of the coefficients with a_{k} = 1 and a_{k′} = 1 then there is no solution with exactly these coefficients being nonzero.

Let A = (C_{1}, …, C_{n_{0}}, C_{n_{0}+1}, …, C_{n_{1}}) be the (|E| × n_{1})-matrix with these cycles as its column vectors. It can be transformed into the reduced row echelon form Ã by Gauß-Jordan elimination. Then exactly the first n rows of Ã are nonzero, where n = rank (A) . Denote the column of the first nonzero element in row i (i = 1, …, n) by p_{i}, i.e., Ã_{i,p_{i}} = 1 and Ã_{i,j} = 0 for all j < p_{i}. By construction, i > i′ implies p_{i} > p_{i′}; the columns p_{i} have a single nonzero entry Ã_{i,p_{i}}. Note that the upper-left n_{0} × n_{0} submatrix of Ã is the identity matrix since B_{<} is linearly independent.

Now we color the columns n_{0} + 1, …, n_{1} of Ã in the following way: (1) Two columns j′ and j′′ (> n_{0}) have the same color if there exists a row i such that Ã_{ij′} = Ã_{ij′′} = 1. (2) Use as many colors as possible. Notice that all such colorings are homomorphic.

Lemma 22. Two cycles C_{j′}, C_{j′′} ∈ R_{=} are ↔-equivalent if and only if the columns j′ and j′′ have the same color in the above coloring of Ã.

Proof. Let P = {p_{1}, …, p_{n}} and P̄ = {j|j = 1, …, n_{1}, j ∉ P }. If j ∈ P̄ then j > n_{0} since the upper left n_{0} × n_{0} block is the identity matrix. When solving equ.(5) we can arbitrarily set a_{j} = 0 or a_{j} = 1 for each j ∈ P̄, while the values a_{p_{i}} are then determined by this choice.

(i) If p_{i} > n_{0} then C_{p_{i}} is essential if and only if Ã_{ij} = 0 for all j ≠ p_{i}.

(ii) Set a_{j} = 1 for exactly one j ∈ P̄, j > n_{0}. Then there is a row i such that Ã_{ij} = 1. This implies Ã_{ip_{i}} = 1. Moreover, the corresponding solution of equ.(5) is minimal. Thus C_{j} ↔ C_{p_{i}}.

(iii) Set a_{j′} = a_{j′′} = 1 for exactly two columns j′, j′′ ∈ P̄. We claim that the corresponding solution a⃗ of equ.(5) is minimal if and only if there exists a row i such that Ã_{ij′} = Ã_{ij′′} = 1. If such a row exists, we have a_{p_{i}} = a_{j′} ⊕ a_{j′′} = 0. Note that a_{j′} and a_{j′′} are the only coefficients that can be freely chosen; hence changing one of

Table 1. Algorithm: Compute ↔-partition 𝔓.

Input: R, B /∗ relevant cycles and a minimal cycle basis ∗/ Output: 𝔓 /∗ interchangeability partition ∗/

1: Sort minimal cycle basis by length: {B_{1}, …, B_{ν}}. 2: Sort relevant cycles by length: {C_{1}, …, C_{n}}. 3: 𝔓 ← ∅. 4: for each cycle length l do 5: B_{<} ← {B ∈ B||B| < l}. 6: R_{=} ← {C ∈ R||C| = l}.

7: A ← (B_{<}, R_{=}). /∗ matrix of cycles ∗/

8: Ã ← reduced row echelon form of A. /∗ Gauß-Jordan elimination ∗/

/∗ Color columns in submatrix B̃ = (Ã_{ij}), j > |B_{<}| as in lemma 22. ∗/

9: Assign each column j > |B_{<}| a different color. 10: for each row i = 1, …, rank (A) do 11: if Ã_{ij′} = Ã_{ij′′} = 1 then 12: Identify the colors of j′ and j′′. 13: for each color c do 14: 𝔓 ← 𝔓 ∪ {all cycles with color c}.

them to 0 would require us to change a_{p_{i}} to 1, i.e., a⃗ is indeed minimal. Conversely if no such row i exists, set a_{j′} = 0. This produces a new solution where all coefficients a_{p_{i}} with Ã_{ip_{i}} = 1 and A_{ij′} = 1 become zero whereas all others remain unchanged. This contradicts minimality.

Paragraphs (ii) and (iii) together imply that two cycles C_{j′}, C_{j′′} ∈ R_{=} are ↔- equivalent if they have the same color.

(iv) Now suppose two cycles C_{j′}, C_{j′′} ∈ R_{=} are ↔-equivalent but the corresponding columns have different colors. By paragraphs (i) and (ii) we may assume that j′, j′′ ∈ P̄. There exists a minimal solution of equ.(5) with a_{j′} = a_{j′′} = 1. Let P̄_{j′} = {j ∈ P̄|a_{j} = 1, j has same color as j′} and define P̄_{j′′} analogously. Then there is no row i, such that Ã_{ik′} = Ã_{ik′′} = 1 for a k′ ∈ P̄_{j′} and k′′ ∈ P̄_{j′′}. Analogously to paragraph (iii), however, this solution cannot be minimal, a contradiction.

Table 1 compiles a procedure that uses lemma 22.

Theorem 23. The ↔-equivalence classes of the set R can be computed by algorithm 1 in O(|B| |R|^{2} |E|) operations.

Proof. Sorting R and B ⊆ R by length requires O(|R| ln |R|) operations. The Gauß-Jordan elimination requires at most O(|R|^{2} |E|) operations. Coloring all the B̃’s needs at most O(|R| |E|) comparisons. Note that this is only a rather crude upper bound for the worst case. The actual requirements are by far smaller for most graphs.

1  2 3 4 5  6 7  8 9  10

Figure 4. The set of relevant cycles consists of C_{0} = (1, 3, 10, 4), C_{1} = (4, 1, 6, 2, 8, 10), C′_{1} = (3, 1, 6, 2, 8, 10), C_{2} = (4, 1, 5, 9, 7, 10), and C′_{2} = (3, 1, 5, 9, 7, 10). We observe C_{0} = C_{1} ⊕ C′_{1} = C_{2} ⊕ C′_{2}. Thus {C_{1}, C′_{1}, C_{2}, C′_{2}} is an ↔-equivalence class. Vismara’s algorithm identifies C_{0},C_{1} and C_{2} as cycle prototypes. Thus we cannot write C_{1} = C_{2} ⊕ ⨁_{Z} such that Z contains only cycle prototypes.

We have assumed in algorithm 1 that a minimum cycle basis B is supplied as input since Vismara’s algorithm for computing R also produces a minimal cycle basis. Of course it could be extracted from the Gauß-Jordan eliminations at virtually no extra cost. Algorithm 1 may require exponential time in terms of |V | since the number of relevant cycles may grow exponentially [15]. Typically, however, there are only O(|V |^{3}) relevant cycles [6].

It is not possible to determine ↔-equivalence with the set R̂ of “cycle prototypes” that is computed in the first step of Vismara’s algorithm. A counterexample is shown in Figure 4.

Appendix

The motivation for the present contribution arises from the search for a suitable energy model for RNA secondary structure computations in the presence of so-called pseudo-knots. A (pseudo-knot free) secondary structure is an outerplanar graph G; hence it has a unique minimum cycle basis B(G) [10]. The standard energy model for this class of molecules assigns additive energy contributions E(C) to the cycles C ∈ B(G), depending on the type of the nucleotides that are represented by the vertices of G [16].

The RNA secondary structure prediction problem can be rephrased as minimizing the energy function E(G) = ∑_{C∈B(G)} E(C) over the class of secondary structure

Figure 5. Two RNA secondary structures with a pseudo-knot. The only difference between the two structures is the exact location of the “middle stem” consisting of the three base pairs that connect the two hairpin loops. The energy contribution for the “pseudo-knot formation” should be attributed to the relevant cycle(s) associated with the “closing pair” of the “middle stem”, indicated by a thick line. On the l.h.s. there is a unique relevant cycle (indicated by the dashed line) associated with the “closing pair” of the middle “stem”. In the example on the r.h.s. we find ten relevant cycles that differ by the ⊕-addition of one or more of the 4-cycles of the rightmost “stem”. It seems natural therefore to associate an energy contribution not with an individual relevant cycle, but rather with an equivalence class W of cycles, in this case with the class of equal length cycles indicated by the dashed lines on the r.h.s.

graphs (which are sub-cubic outerplanar graphs satisfying a few further restrictions, see e.g. [13, 17] for details). Pseudo-knots violate outerplanarity and in general lead to graphs with a non-unique minimum cycle basis, Figure 5. The set R of relevant cycles, i.e., the union of all minimum cycle bases [15] seems to be a good candidate for extending the energy model. However, as the example in Figure 5 shows, sometimes there is a large class of relevant cycles associated with what biophysically is a single structural element. These are exactly the interchangeable cycles.

It seems natural therefore to average over contributions of interchangeable cycles or to define the energy parameters in such a way that all interchangeable cycles contribute the same energy. Hence we suggest that

E(G) = ∑_{W∈𝔓} \frac{knar (W)}{|W|} ∑_{C∈W} E(C)  (6)

serves as a suitable generalization of the standard energy model for nucleic acid structures.

Acknowledgements

This work was supported in part by the Austrian Fonds zur Förderung der Wissenschaftlichen Forschung Proj. 12591-INF and by the European Commission within the framework of the Biotechnology Program (BIO-4-98-0189). Input from two anonymous referees is gratefully acknowledged.

References

[1] W.-K. Chen. On vector spaces associated with a graph. SIAM J. Appl. Math., 20:525–529, 1971.

[2] D. M. Chickering, D. Geiger, and D. Heckerman. On finding a cycle basis with a shortest maximal cycle. Inform. Processing Let., 54:55–58, 1994.

[3] L. O. Chua and L. Chen. On optimally sparse cycle and coboundary basis for a linear graph. IEEE Trans. Circuit Theory, 20:54–76, 1973.

[4] G. A. Dirac. On rigid circuit graphs. Abh. Math. Sem. Hamburg, 25:71–76, 1961.

[5] G. M. Downs, V. J. Gillet, J. D. Holliday, and M. F. Lynch. Review of ring perception algorithms for chemical graphs. J. Chem. Inf. Comput. Sci., 29:172– 187, 1989.

[6] P. M. Gleiss and P. F. Stadler. Relevant cycles in biopolymers and random graphs. Presented at the Fourth Slovene International Conference in Graph Theory, Bled, Slovenia, 1999.

[7] D. Hartvigsen and R. Mardon. The all-pair min-cut problem and the minimum cycle basis problem on planar graphs. SIAM J. Discr. Math., 7:403–418, 1994.

[8] J. D. Horton. A polynomial-time algorithm to find the shortest cycle basis of a graph. SIAM J. Comput., 16:359–366, 1987.

[9] A. Kaveh. Structural Mechanics: Graph and Matrix Methods. Research Studies Press, Exeter, UK, 1992.

[10] J. Leydold and P. F. Stadler. Minimal cycle basis of outerplanar graphs. Electr.

J. Comb., 5:R16, 1998. See http://www.combinatorics.org.

[11] J. Oxley. Graphs and series-parallel networks. In N. White, editor, Theory of Matroids, volume 26 of Encyclopedia of Mathematics and Applications, pages 97–126. Cambridge University Press, Cambridge, UK, 1986.

[12] M. Plotkin. Mathematical basis of ring-finding algorithms in CIDS. J. Chem. Doc., 11:60–63, 1971.

[13] P. F. Stadler and C. Haslinger. RNA structures with pseudo-knots: Graphtheoretical and combinatorial properties. Bull. Math. Biol., 61:437–467, 1999.

[14] C. Thomassen. Embeddings and minors. In R. Graham, M. Grötschel, and L. Lovász, editors, Handbook of Combinatorics, pages 301–349. North-Holland, Amsterdam, 1995.

[15] P. Vismara. Union of all the minimum cycle bases of a graph. Electr. J. Comb., 4:73–87, 1997. Paper No. #R9 (15 pages).

[16] A. E. Walter, D. H. Turner, J. Kim, M. H. Lyttle, P. Müller, D. H. Mathews, and M. Zuker. Co-axial stacking of helixes enhances binding of oligoribonucleotides and improves predicions of RNA folding. Proc. Natl. Acad. Sci. USA, 91:9218– 9222, 1994.

[17] M. S. Waterman. Secondary structure of single-stranded nucleic acids. Adv. Math. Suppl. Studies, 1:167–212, 1978.

[18] D. J. A. Welsh. Matroids: Fundamental concepts. In R. Graham, M. Grötschel, and L. Lovász, editors, Handbook of Combinatorics, pages 483–526. North-Holland, Amsterdam, 1995.