Christin Otto, Peter Recht

Operations Research and Business Informatics TU Dortmund 44221 Dortmund, Germany

christin-maria.otto@tu-dortmund.de, peter.recht@tu-dortmund.de

Let G = (V, E) be an undirected multigraph without loops. The maximum cycle packing problem is to find a collection Z ^∗ = {C1, ..., Cs} of edge-disjoint cycles Cⁱ ⊂ G of maximum cardinality ν(G). In general, this problem is N P-hard. An approximation algorithm for computing ν(G) for 2-connected graphs is presented, which is based on splits of G. It essentially uses the representation of the 3-connected components of G by its SPR-tree. It is proved that for generalized series-parallel multigraphs the algorithm is optimal, i.e. it determines a maximum cycle packing Z ∗ in linear time.

Keywords: maximum cycle packing, decomposition, SPR-trees, edge-disjoint cycle

Mathematics Subject Classification : 05C38, 05C70

DOI: 10.5614/ejgta.2019.7.1.11

1. Introduction

Let G = (V (G), E(G)) be a finite and undirected graph with vertex set V (G) and edge set E(G) which may contain multiple edges but no loops. A graph G⁰ = (V 0 , E⁰ ) is a subgraph of G (G⁰ ⊆ G), if V ⁰ ⊆ V and E ⁰ ⊆ E. A subgraph G⁰ = (V 0 , E⁰ ) ⊂ G is induced by E ⁰ ⊂ E (G⁰ = G|E⁰) if V 0 consists of all vertices that are incident with edges in E 0 . Similarly, G⁰ = (V 0 , E⁰ ) ⊂ G is induced by V ⁰ ⊂ V (G⁰ = G|^{V 0}) if E 0 consists of all edges e ∈ E, that have both endvertices in V 0 . We will write G \ V 0 := G|^V \^{V 0} and G \ E 0 := G|E\E⁰, respectively. For u ∈ V the degree δG(u) is the number of its incident edges in G. A path P of length r ≥ 0 is a sequence of distinct edges (e1, . . . , er) such that eⁱ = (vi−1, vi) ∈ E(G) where the vertices v0, . . . , v^r ∈ V (G)

Received: 2 February 2017, Revised: 26 September 2018, Accepted: 23 December 2018.

are distinct. We sometimes say P is a v0-vr-path to emphasize the first and the last vertex of a path. A cycle C of length r ≥ 2 is a sequence (e1, . . . , er−1, er) such that (e1, . . . , er−1) is a path of length r − 1 and e^r = (vr−1, v0). Since P can be considered as a subgraph of G we sometimes say that P is induced by its edgeset E(P). A graph G is connected if for each pair of vertices v, w ∈ V there is a v-w-path in G. A set S ⊂ V is called a k-separator of G (k ≥ 0, |S| = k) if G|^V \^S is not connected. A connected graph G is called k-connected if there is no (k − 1)-separator in G. The maximum 1-connected subgraphs of G are called 1-components. The maximum 2-connected subgraphs of G are called blocks. We say G is k-separable if there exist subgraphs G1, G² of G such that G = G¹ ∪ G² with |V (G1) ∩ V (G2)| = k, E(G1) ∩ E(G2) = ∅ and |E(G1)| ≥ k, |E(G2)| ≥ k. The pair {G1, G2} is then called a k-separation of G. Two subgraphs G⁰ = (V 0 , E⁰ ) and G⁰⁰ = (V ⁰⁰, E⁰⁰) are called edge-disjoint if E ⁰ ∩ E ⁰⁰ = ∅. A packing of edge-disjoint cycles of cardinality s in G is a set Z = {C1, . . . , Cs} of cycles that are mutually edge-disjoint. A cycle packing Z ^∗ of maximum cardinality is called a maximum cycle packing. Its cardinality |Z^∗ | is denoted by ν(G).

Packing edge-disjoint cycles in graphs is a classical graph-theoretical problem. There is a large amount of literature concerning cycle packing problems for example [12], [11], [10], [1], [20], [7], [6], [19], [18]. In [14], [2] and [8] simple approximation algorithms are described since cycle packing problems are typically hard [14].

The basic idea of this paper is to decompose G into suitable subgraphs Gⁱ and relate maximum cycle packings Zⁱ of the Gⁱ to a maximum cycle packing Z ^∗ of G. In the case that Gⁱ are the 1-components it holds that Z ^∗ = S Zⁱ and ν(G) = Pν(Gi). If G is decomposed into blocks Bi it holds that ν(G) = Pν(Bi). If G is 2-connected an appropriate tool to represent G by its 3-connected components is the SPR-tree [5]. In Section 2 this tool is used to obtain an algorithm that provides an approximation of a maximum cycle packing of G. The proof of optimality of the algorithm for general series-parallel graphs is given in Section 3.

2. Cycle packing by using SPR-trees

In [2] a greedy type algorithm was suggested for the determination of a large number of edgedisjoint cycles in an arbitrary graph G (see also [14]). Its basic idea is to search for the shortest cycle C in G, then delete it from G and delete also edges that cannot be contained in a cycle of G \ C. This procedure is continued until there are no edges left. The set of successively deleted cycles finally provides the approximation of a maximum cycle packing of G (Algorithm 1). The algorithm has approximation ratio O(log n) (see [2]).

In the special case that G is 2-connected we, additionally, will exploit the splits of G into 3 components during the algorithmic procedure. By this we can relate the edge-disjoint cycles within each of these components to cycles in a cycle packing of G. Let G be a 2-connected multigraph and let {G1, G2} be a 2-separation of G. If {u, v} = V (G1) ∩ V (G2), we call the 2-separation a split, if G¹ or G² has no 0- or 1-separator and G¹ \{u, v} or G² \{u, v} is non-empty and connected [16]. In [21] it was proved that 2-connected graphs that have no splits are either 3-connected or cycles of length ≥ 3 or a bundle of parallel edges between two vertices, respectively. For a split {G1, G2} let G⁰ 1 and G^{0 2} be the graphs obtained from G¹ and G² by adding an edge (u, v) to each of them where (u, v) is determined by the common vertices {u, v} = V (G1) ∩ V (G2). The added

Algorithm 1 Greedy algorithm for the maximum cycle packing problem

Require: Biconnected multigraph G = (V, E) without loops.
Ensure: Cycle packing C of size ν(G).
1: C ← ∅ and ν(G) ← 0
2: while G 6= ∅ do
3: for all vertices v ∈ V with δ(v) ≤ 1 do
4: delete v
5: end for
6: for all vertices v ∈ V with δ(v) = 2 do
7: replace e
                  0 = (u, v) and e
                                00 = (v, w) by e = (u, w)
8: end for
9: search for a shortest cycle C ∈ G
10: C ← C ∪ C
11: ν(G) ← ν(G) + 1
12: for all edges e ∈ C do
13: delete e ∈ G
14: end for
15: end while
16: return Cycle packing C and lower bound ν(G) of ν(G).

edges are called virtual edges. Since G⁰ 1 and G⁰ 2 are 2-connected one may repeat the split process as long as the obtained graphs admit splits. Each of the resulting graphs finally constructed in this way is called a split component of G. A split component contains edges from E and some virtual edges determined by its consecutive split operations. In [15] and [21] it was shown, that split components of G are uniquely determined and independent of the sequence in which consecutive split operations were performed.

By this G can be represented using the SPR-tree T (G) = (M, A) of G as defined in [3], which is an alternative to the definition of [5, 9]. If no ambiguity is possible we write T for short. A SPR-tree T of a 2-connected multigraph G is the smallest tree with the following properties

• 1. To every node¹ µ ∈ M a multigraph G^µ = (Vµ, Eµ) (called skeleton of µ) is associated.
• 2. Depending on their skeletons the nodes of T are of one of the following three types
  • µ is a S-node if G^µ is a cylce of length ≥ 3,
  • µ is a P-node if G^µ is a bundle of parallel edges,
  • µ is a R-node if G^µ is a simple 3-connected graph.
• 3. There is an edge (µ, µ⁰ ) ∈ A if and only if there is u, v ∈ V such that G^µ and Gµ⁰ have e¯(µ,µ0) := (u, v) as a common virtual edge.
• 4. The graph G can be recovered by applying the following operation on the nodes of T : for (µ, µ⁰ ) ∈ A set G(µ,µ0) := (G^µ \ e¯(µ,µ0)) ∪ (Gµ⁰ \ e¯(µ,µ0)) and merge the two nodes µ, µ⁰ to a new single node.

In [3] it was proved that a SPR-tree T of a 2-connected multigraph G exists and is unique. Moreover, it has neither two adjacent S-nodes nor two adjacent P-nodes. Since there is a strong

¹The vertices in T are usually called nodes.

relation between SPR-trees and SPQR-trees introduced in [4], its size as well as the complexity of its determination is linear (in \(\mathcal{O}(|V| + |E|)\)) (cf. [3]).

In the sequel we assume that G is a 2-connected multigraph with no loops. Let \(\mathcal{T}\) be the SPR-tree of G and \(\mu\) be a leaf in \(\mathcal{T}\) (i.e. a node in \(\mathcal{T}\) such that \(\delta_{\mathcal{T}}(\mu)=1\)). The following approximation procedure applies Algorithm 1 in some of the iterations. It essentially exploits the SPR-tree representation of G and uses property 4 of \(\mathcal{T}\) for an iterative construction of a large cycle packing \(\mathcal{Z}\) in G. These cycles will be constructed from paths \(\mathcal{P}_{\mu}\) for \(\mu \in \mathcal{T}\). We initialize the sets \(\mathcal{P}_{\mu}\) by \(\mathcal{P}_{\mu} = \{P(e) \mid e \text{ is a real edge in } E_{\mu}\}\) with P(e) := e and \(\mathcal{Z} = \emptyset\).

During the procedure leaf nodes \(\mu\) and the corresponding set \(\mathcal{P}_{\mu}\) are successively inspected. Leaf nodes of S-type are always processed first, followed by R-leaves and P-leaves. Note, that for a leaf node \(\mu \in M\) there is a unique node \(\mu' \in M\) such that \((\mu, \mu') \in A\) and the edge set \(E_{\mu}\) contains exactly one virtual edge \(\bar{e}_{(\mu,\mu')} = (u,v)\). Within the procedure we set \(\operatorname{pred}(\mu) := \mu'\) the predecessor of \(\mu\). An inspection looks for the existence of edge-disjoint cycles on the real edges in \(E_{\mu}\). Such cycles correspond to edge-disjoint cycles in G. If there still remains an u-v-path on the real edges in \(E_{\mu}\) there remains a corresponding u-v-path \(P_{uv}\) in G. In this case the virtual edge \(\bar{e}_{(\mu,\mu')}\) in \(E_{\mu'}\) is replaced by the real edge (u,v) and P((u,v)) is set to \(P_{uv}\). If the virtual edge can not be replaced in such a way, it is deleted from \(E_{\mu'}\).

Depending on the type of leaf node \(\mu\) and its edge set \(E_{\mu}\) the edge set \(E_{\mu'}\) of \(pred(\mu)\) is treated differently according to the following rules:

• \(1_S\) \(\mu\) is S-node: If the real edges in \(E_{\mu}\) induce an u-v-path in \(E_{\mu}\), replace \(\bar{e}_{(\mu,\mu')} \in E_{\mu'}\) by the real edge (u,v). Assign the u-v-path induced by \(\bigcup \{E(P) \mid P \in \mathcal{P}_{\mu}\}\) to P((u,v)). Set \(\mathcal{P}_{\mu'} = \mathcal{P}_{\mu'} \cup P((u,v))\), \(\nu_{\mu} = 0\) and delete \(\mu\) from \(\mathcal{T}\).
• \(2_R\) \(\mu\) is R-node: Determine cycle packings \(\mathcal{C}_1\) and \(\mathcal{C}_2\) for the graphs induced by \(E_\mu\) and \(E_\mu \setminus \bar{e}_{(\mu,\mu')}\), respectively. Set \(\nu_\mu = |\mathcal{C}_2|\), add the corresponding edge-disjoint cycles in G to \(\mathcal{Z}\) and delete the related paths from \(\mathcal{P}_\mu\). If \(|\mathcal{C}_1| = |\mathcal{C}_2|\) delete \(\bar{e}_{(\mu,\mu')} \in E_{\mu'}\). If \(|\mathcal{C}_1| > |\mathcal{C}_2|\), there is an u-v-path in \(E_\mu\), not contained in any of the cycles of \(\mathcal{C}_2\). Replace \(\bar{e}_{(\mu,\mu')} \in E_{\mu'}\) by the real edge (u,v). Assign the u-v-path \(P_{uv}\) induced by \(\bigcup \{E(P) \mid P \in \mathcal{P}_\mu\}\) to P((u,v)). Set \(\mathcal{P}_{\mu'} = \mathcal{P}_{\mu'} \cup P((u,v))\) and delete \(\mu\) from \(\mathcal{T}\).

\(3_P\) \(\mu\) is P-node:

• (i) If \(|E_{\mu}|\) is even, there is a cycle packing \(\mathcal{C}_P\) with \(\nu_{\mu} = \frac{|E_{\mu}|}{2} 1\) cycles of length 2. Add the corresponding edge-disjoint cycles in G to \(\mathcal{C}\). Then delete the related paths from \(\mathcal{P}_{\mu}\). There remains an real edge e in \(E_{\mu}\), not contained in any of the cycles of \(\mathcal{C}_P\). Replace \(\bar{e}_{(\mu,\mu')} \in E_{\mu'}\) by the real edge (u,v) and assign the u-v-path \(P_{uv}\) induced by e to P((u,v)). Set \(\mathcal{P}_{\mu'} = \mathcal{P}_{\mu'} \cup P((u,v))\) and delete \(\mu\) from \(\mathcal{T}\).
• (ii) If \(|E_{\mu}|\) is odd, there is a cycle packing \(C_P\) with \(\nu_{\mu} = \frac{|E_{\mu}|-1}{2}\) cycles of length 2. Add the induced edge-disjoint cycles in G to C. Further delete \(\bar{e}_{(\mu,\mu')} \in E_{\mu'}\) and delete \(\mu\) from T.

The procedure terminates inspecting the final node:

Algorithm 2 Approximation algorithm for the maximum cycle packing problem

Require: Biconnected multigraph G without loops. Ensure: Lower bound \(\nu(G)\) for the maximum cycle packing number \(\nu(G)\). 1: \(\mathcal{T}_G \leftarrow \mathrm{SPR}(G)\)2: \(\mathcal{C} \leftarrow \emptyset\), \(\underline{\nu}(G) \leftarrow 0\) and \(\mathcal{P}_{\mu} \leftarrow \emptyset \quad \forall \mu \in M\)3: while \(\exists\) SPR-node \(\mu\) in \(\mathcal{T}\) do 4: for all S-leaves \(\mu\) do 5: \(\mu' := pred(\mu)\)6: if \(\delta(v) = 2 \ \forall v \in V_{\mu}\) then 7: replace \(\bar{e}_{(\mu,\mu')} \in E_{\mu'}\) by real edge \(\mathcal{P}_{\mu'} \leftarrow \mathcal{P}_{\mu'} \cup P(\bar{e}_{(\mu,\mu')})\)8: 9: \(\nu_{\mu} \leftarrow 0\) and \(\mathcal{T} \leftarrow \mathcal{T} \setminus \mu\)10: 11: \(\underline{\nu}(G) \leftarrow \underline{\nu}(G) + \nu_{\mu}\)12: end for 13: for all R-leaves \(\mu\) do 14: \(\mu' := pred(\mu)\)15: \(\mathcal{C}_1 \leftarrow \text{Algorithm } 1(G_u)\)\(C_2 \leftarrow \text{Algorithm } 1(G_{\mu} \setminus \bar{e}_{(\mu,\mu')})\)16: 17: if \(|\mathcal{C}_1| == |\mathcal{C}_2|\) then 18: delete \(\bar{e}_{(\mu,\mu')} \in E_{\mu'}\)19: else if \(|\mathcal{C}_1| > |\mathcal{C}_2|\) then 20: replace \(\bar{e}_{(\mu,\mu')} \in E_{\mu'}\) by real edge \(\mathcal{P}_{\mu'} \leftarrow \mathcal{P}_{\mu'} \cup P(\bar{e}_{(\mu,\mu')})\)21: 22: \(\nu_{\mu} \leftarrow |\mathcal{C}_2|\) and \(\mathcal{T} \leftarrow \mathcal{T} \setminus \mu\)23: \(\underline{\nu}(G) \leftarrow \underline{\nu}(G) + \nu_{\mu} \text{ and } \mathcal{C} \leftarrow \mathcal{C} \cup \mathcal{C}_2\)24: 25: end for 26: for all P-leaves \(\mu\) do 27: \(\mu' := pred(\mu)\)28: if \(|E_{\mu}|\) is not even then \(\nu_{\mu} \leftarrow \frac{|E_{\mu}|-1}{2}\)29: delete \(\bar{e}_{(\mu,\mu')}\) in \(E_{\mu'}\)30: else if \(|E_{\mu}|\) is even then 31: \(\nu_{\mu} \leftarrow \frac{|E_{\mu}|}{2} - 1\)32: replace \(\dot{\bar{e}}_{(\mu,\mu')}\) in \(E_{\mu'}\) by real edge 33: 34: \(\mathcal{P}_{\mu'} \leftarrow \mathcal{P}_{\mu'} \cup P(\bar{e}_{(\mu,\mu')})\)35: 36: \(\underline{\nu}(G) \leftarrow \underline{\nu}(G) + \nu_{\mu} \text{ and } \mathcal{T} \leftarrow \mathcal{T} \setminus \mu\)\(\mathcal{C} \leftarrow \mathcal{C} \cup \{\{P^{(2i-1)}, P^{(2i)}\} \mid P^{(i)} \in \mathcal{P}_u \forall i = 1, \dots, \nu_u\}\)37: 38: end for 39: for the final node \(\mu\) do 40: if \(\mu\) is S-leaf and \(\delta(v) = 2 \ \forall v \in V_{\mu}\) then \(\nu_{\mu} \leftarrow 1 \text{ and } \mathcal{C} \leftarrow \mathcal{C} \cup P|_{E(\bigcup_{e \in E_{\mu}} P(e))}\)41: 42: else if \(\mu\) is R-leaf then \(\mathcal{C}_1 \leftarrow \text{Algorithm } 1(G_\mu), \nu_\mu \leftarrow |\mathcal{C}_\infty| \text{ and } \mathcal{C} \leftarrow \mathcal{C} \cup \mathcal{C}_1\)43: else if \(\mu\) is P-leaf then 44: \(\nu_{\mu} \leftarrow \lfloor \frac{|E_{\mu}|}{2} \rfloor \text{ and } \mathcal{C} \leftarrow \mathcal{C} \cup \{\{P^{(2i-1)}, P^{(2i)}\} \mid P^{(i)} \in \mathcal{P}_{\mu} \forall i = 1, \dots, \nu_{\mu}\}\)45: 46: 47: \(\underline{\nu}(G) \leftarrow \underline{\nu}(G) + \nu_{\mu} \text{ and } \mathcal{T} \leftarrow \mathcal{T} \setminus \mu\)48: end for 49: end while

F If \(\mu\) is the final node, determine a cycle packing \(C_F\) in the graph induced by \(E_{\mu}\). Set \(\nu_{\mu} = |C_F|\) and add the induced edge-disjoint cycles in G to C.

Theorem 2.1. Algorithm 2 determines a cycle packing Z of G of cardinality

\[|\mathcal{Z}| = \sum_{\mu \in \mathcal{T}} \nu_{\mu}.\]

Proof. Let \(\mathcal{T}\) be the SPR-tree of G.

When inspecting a S-node \(\mu\), the real edges in \(E_{\mu}\) never induce a cycle, hence, \(\nu_{\mu}=0\). If the real edges induce an u-v-path in \(E_{\mu}\) the corresponding u-v-path \(P_{uv}\) in G may contribute to an additional cycle C in \(\mathcal{Z}\). Therefore, the virtual edge \(\bar{e}_{(\mu,\mu')}\) in \(E_{\mu'}\) is replaced by the real edge (u,v), P((u,v)) is set to \(P_{uv}\) and \(\mu\) is deleted from \(\mathcal{T}\). The possible cycle C might be determined when inspecting \(\mu'\).

When inspecting a R-node \(\mu\), two cycle packings \(\mathcal{C}_1\) and \(\mathcal{C}_2\) are determined for \(E_\mu\) and \(E_\mu \setminus \bar{e}_{(\mu,\mu')}\), respectively. \(E_\mu\) induces at least a cycle packing of cardinality \(\nu_\mu = |\mathcal{C}_2|\) in G. If \(|\mathcal{C}_1| > |\mathcal{C}_2|\), P((u,v)) may also contribute to one more cycle C in \(\mathcal{Z}\). Therefore the virtual edge \(\bar{e}_{(\mu,\mu')}\) is replaced in \(E_{\mu'}\) by (u,v) and a C might be determined when inspecting \(\mu'\).

When inspecting a P-node \(\mu\), different pairs of real edges in \(E_{\mu}\) always induce edge-disjoint cycles in G. If \(|E_{\mu}|\) is even, there are \(\nu_{\mu} = \frac{|E_{\mu}|}{2} - 1\) of such pairs. The path \(P_{uv}\) induced by the remaining real edge may contribute to an additional cycle C in \(\mathcal{Z}\). For this reason the virtual edge \(\bar{e}_{(\mu,\mu')}\) is replaced in \(E_{\mu'}\) by (u,v) and C might be determined when inspecting \(\mu'\). If \(|E_{\mu}|\) is odd, there are \(\nu_{\mu} = \frac{|E_{\mu}|-1}{2}\) pairs of real edges inducing the same number of additional cycles in \(\mathcal{Z}\). \(\square\)

Algorithm 2 has approximation ratio \(\mathcal{O}(\log n)\), the same as Algorithm 1. If the SPR-tree \(\mathcal{T}\) of G has no R-nodes we next proof in Section 3 that Algorithm 2 is optimal.

3. Proof of optimality for General Series-Parallel Graphs

Let G be a multigraph without loops. G is called generalized series-parallel, if it can be reduced to the \(K_2\) by performing a sequence of simple operations:

• (a) Replace two parallel edges by a single edge;
• (b) replace two edges with a common incident node of degree 2 by a single edge;
• (c) delete vertices of degree 1.

If there is no vertex of degree 1 to delete, G is called series-parallel. It is known that outerplanar graphs are generalized series-parallel [13]. A 2-connected generalized series-parallel multigraph G is reducable to \(K_2\) by only performing operations (a) and (b). We will assume the input graph is 2-connected, since the algorithm could be launched on each block of G. The SPR-tree \(\mathcal{T}\) of G has no R-nodes (cf. [17]). In this case the iterations of Algorithm 2 reflect a systematic sequence of operations of type (a) and (b) for the reduction of G. It leads to optimality of \(\mathcal{Z}\).

Theorem 3.1. Let G be a 2-connected, generalized series-parallel multigraph without loops. Then

\[\nu(G) = \sum_{\mu \in \mathcal{T}} \nu_{\mu},\]

i.e. Algorithm 2 determines a maximum cycle packing of G.

Proof. For the proof we will use induction on the number N of nodes in the SPR-tree \(\mathcal{T}(G)\) of G. Let N=1, i.e. \(\mathcal{T}(G)\) is either a P-node or a S-node, respectively. Hence, the series-parallel multigraph G is either a set of r parallel edges \((r\geq 3)\) or a cycle of length \(\geq 3\). In the first case \(\nu(G)=\lfloor \frac{r}{2}\rfloor\), in the second case \(\nu(G)=1\). In both cases \(\nu(G)\) is the output of Algorithm 2 (step F). Let \(N\geq 2\) and let us assume that Algorithm 2 determines \(\nu(G')\) for all series-parallel multigraphs G' such that \(\mathcal{T}(G')\) has at most N-1 nodes. Let G be a series-parallel multigraph such that \(\mathcal{T}(G)\) has N nodes. Now, we apply Algorithm 2. When selecting the first node \(\mu\in\mathcal{T}(G)\) for inspection, the following cases can occur.

• (a) \(\mu\) is a S-leaf. Then Algorithm 2 treats \(\mu\) according \((1_S)\). The multigraph \(G' = G \setminus (E_{\mu} \setminus \bar{e}_{(\mu,\mu')}) \cup (u,v)\) is series-parallel and \(\mathcal{T}(G') = \mathcal{T}(G) \setminus \mu\), i.e. \(\mathcal{T}(G')\) has N-1 nodes. Moreover, \(\nu(G') = \nu(G)\). By hypothesis \(\nu(G') = \sum_{\tilde{\mu} \in \mathcal{T}(G')} \nu_{\tilde{\mu}}\) and therefore \(\sum_{\tilde{\mu} \in \mathcal{T}(G)} \nu_{\tilde{\mu}} = \sum_{\tilde{\mu} \in \mathcal{T}(G')} \nu_{\tilde{\mu}} + \nu_{\mu} = \nu(G') + 0 = \nu(G)\).
• (b) \(\mu\) is a P-leaf in \(\mathcal{T}(G)\), then all leaf nodes are P-nodes.
  • (b1) There exists at least one leaf \(\mu\) with an odd number of real edges, i.e. \(|E_{\mu}|\) is even. Its predecessor \(\mu'\) is a S-node. Algorithm 2 treats \(\mu\) according \((3_P,(i))\). The multigraph \(G' = G \setminus (E_{\mu} \setminus \bar{e}_{(\mu,\mu')}) \cup (u,v)\) is series-parallel and \(\mathcal{T}(G') = \mathcal{T}(G) \setminus \mu\), i.e. \(\mathcal{T}(G')\) has N-1 nodes. Moreover \(\nu(G') = \nu(G) (\frac{|E_{\mu}|}{2} 1)\). By hypothesis \(\nu(G') = \sum_{\tilde{\mu} \in \mathcal{T}(G')} \nu_{\tilde{\mu}}\) and, therefore, \(\sum_{\tilde{\mu} \in \mathcal{T}(G)} \nu_{\tilde{\mu}} = \sum_{\tilde{\mu} \in \mathcal{T}(G')} \nu_{\tilde{\mu}} + \nu_{\mu} = \nu(G') + (\frac{|E_{\mu}|}{2} 1) = \nu(G)\).
  • (b2) All P-leaves have an even number of real edges. Then a leaf \(\mu\) is treated according \((3_P,(ii))\). Let \(\mu' = pred(\mu)\). We assume that \(\mu'\) is adjacent to \(k \geq 1\) P-leaves \(\mu_1,\ldots,\mu_k\) (let \(\mu_1 = \mu\)). Let \(\hat{E}\) be the set of real edges in \(\bigcup_{i \in \{1,\ldots,k\}} E_{\mu_i} \cup E_{\mu'}\). Then for the subgraph \(\hat{G}\) induced by \(\hat{E}\) we get \(\nu(\hat{G}) = \sum_{i \in \{1,\ldots,k\}} \nu_{\mu_i}\). If \(E \setminus \hat{E} = \emptyset\), \(\mathcal{T}(G) = \mathcal{T}(\hat{G})\) and \(\nu(G) = \sum_{i \in \{1,\ldots,k\}} \nu_{\mu_i} = \sum_{\tilde{\mu} \in \mathcal{T}(G)} \nu_{\tilde{\mu}}\). If \(E \setminus \hat{E} \neq \emptyset\) then for the graph G' induced by \(E \setminus \hat{E}\) we have \(\nu(G') = \nu(G) \sum_{i \in \{1,\ldots,k\}} \nu_{\mu_i}\). Now we show that G' is seriesparallel. In \(\mathcal{T}(G) \setminus (\bigcup_{i \in \{1,\ldots,k\}} \mu_i \cup \mu') \mu'\) must have a predecessor \(\mu'' = pred(\mu)\). \(\mu''\) is a P-node and must contain at least two parallel edges with endvertices, say u'', v''. One of them corresponds to the subgraph \(\hat{G}\) when recovering G from \(\mathcal{T}(G)\) (according to property 4). Since G is series-parallel, \(G'' = G' \cup (u'', v'')\) is series-parallel. Since there is at least one more virtual edge parallel to (u'', v'') in \(E_{\mu''}\), there must be a subgraph \(\tilde{G} \subset G\) such that \(\tilde{G}\) is reducible to a parallel edge of (u'', v'') and \(E(\tilde{G}) \cap E(\hat{G}) = \emptyset\). According to property (b) of definition \(G'' \setminus (u'', v'') = G'\) must be series-parallel. Obviously \(\mathcal{T}(G') = \mathcal{T}(G) \setminus (\bigcup_{i \in \{1,\ldots,k\}} \mu_i \cup \mu')\). \(\mathcal{T}(G')\) has N (k+1) nodes. By hypothesis \(\nu(G'') = \sum_{\tilde{\mu} \in \mathcal{T}(G')} \nu_{\tilde{\mu}}\) and \(\nu(G) = \sum_{\tilde{\mu} \in \mathcal{T}(G')} \nu_{\tilde{\mu}} + \sum_{i \in \{1,\ldots,k\}} \nu_{\mu_i} = \sum_{\tilde{\mu} \in \mathcal{T}(G)} \nu_{\tilde{\mu}}\).

The SPQR-tree of a 2-connected multigraph can be determined in linear time [9]. This holds also for the SPR-tree (see [3]) and we immediately get:

Corollary 3.1. If G is a 2-connected, generalized series-parallel multigraph without loops, then a maximum cycle packing of G can be determined in linear time.

References

• [1] N. Alon, C. McDiarmid, and M. Molloy, Edge-disjoint cycles in regular directed graphs, J. Graph Theory 22 (1996), 231–237.
• [2] A. Caprara, A. Panconesi, and R. Rizzi, Packing cycles in undirected graphs, J. Algorithms 48 (2003), 239–256.
• [3] M. Chimani, Computing Crossing Numbers, PhD thesis, TU Dortmund (2008). http:// hdl.handle.net/2003/25955
• [4] G. Di Battista and R. Tamassia, Incremental planarity testing, 30th Annual Symposium on Foundations of Computer Science (1989), 436–441.
• [5] G. Di Battista and R. Tamassia, On-line maintenance of triconnected components with SPQRtrees, Algorithmica 15 (1996), 302–318.
• [6] G. Dirac and P. Erdos, On the maximal number of independent circuits in a graph, ˝ Acta Mathematica Academiae Scientiarum Hungarica 14 (1963), 79–94.
• [7] P. Erdos and L. P ˝ osa, On the maximal number of disjoint circuits of a graph, ´ Publicationes Mathematicae Debrecen 9 (1962), 3–12.
• [8] Z. Friggstad and M.R. Salavatipour, Approximability of packing disjoint cycles, Algorithmica 60 (2011), 395–400.
• [9] C. Gutwenger and P. Mutzel, A linear time implementation of SPQR-trees, Proceedings of the 8th International Symposium on Graph Drawing (2000), 77–90.
• [10] L. Hao, Edge disjoint cycles in graphs, J. Graph Theory 13 (1989), 313–322.
• [11] J. Harant, D. Rautenbach, P. Recht, and F. Regen, Packing edge-disjoint cycles in graphs and the cyclomatic number, Discrete Math. 310 (2010), 1456–1462.
• [12] J. Harant, D. Rautenbach, P. Recht, I. Schiermeyer, and E.-M. Sprengel, Packing disjoint cycles over vertex cuts, Discrete Math. 310 (2010), 1974–1978.
• [13] N.M. Korneyenko, Combinatorial algorithms on a class of graphs, Discrete Appl. Math. 54 (1994), 215–217.

• [14] M. Krivelevich, Z. Nutov, M. R. Salavatipour, J. Verstraete, and R. Yuster, Approximation algorithms and hardness results for cycle packing problems, ACM Transactions on Algorithms (TALG) 3 (2007), 48.
• [15] S. Mac Lane, A structural characterization of planar combinatorial graphs, Duke Mathematical Journal 3 (1937), 460–472.
• [16] B. Mohar, Obstructions for the disk and the cylinder embedding extension problems, Combinatorics, Probability and Computing 3 (1994), 375–406.
• [17] P. Mutzel, The SPQR-tree data structure in graph drawing, Proceedings of the 30th International Conference on Automata, Languages and Programming (2003), 34–46.
• [18] D. Rautenbach and F. Regen, On packing shortest cycles in graphs, Information Processing Letters 109 (2009), 816–821.
• [19] P. Recht and E.-M. Sprengel, Packing Euler graphs with traces, Operations Research Proceedings 2011 (2012), 53–58.
• [20] P. Recht and S. Stehling, On maximum cycle packings in polyhedral graphs, Electron. J. Graph Theory Appl. 2 (1) (2014), 18–31.
• [21] W.T. Tutte, Connectivity in graphs (1966).