Maximum cycle packing using SPR-trees - Christin Otto; Peter Recht (GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB, 2019)
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.