Maximum cycle packing using SPR-trees

Christin Otto (Operations Research and Business Informatics, TU Dortmund, 44221 Dortmund, Germany)
Peter Recht (Operations Research and Business Informatics, TU Dortmund, 44221 Dortmund, Germany)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 7, No 1 (2019): Electronic Journal of Graph Theory and Applications

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.