Maximum cycle packing using SPR-trees

Abstract

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 Ci subset G of maximum cardinality v(G). In general, this problem is NP-hard. An approximation algorithm for computing v(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