# Algorithms for heaviest edge-disjoint cycle collection contained in graph's set of edges

given a biconnected symmetric graph with weighted edges,
what is the algorithmic complexity of determining a set of pairwise edge-disjoint cycles with maximal sum of edge weights if there are no other constraints besides edge-disjointness of the cycles and maximal weightsum of their edges?

Determing such a set of cycles is a stepping stone in an algorithm for determining a heaviest euler tour in complete symmetric graphs with $$n=2k$$ vertices (which isn't eulerian), which in turn would yield an improved heuristic for the non-eulerian windy postman problem.

## 1 Answer

The problem is NP-hard, even in the unweighted case (all weights equal to $$1$$). Indeed, given a graph $$G$$ and an integer $$k$$, deciding if $$G$$ contains an Eulerian subgraph with at least $$k$$ edges is NP-complete. However, the problem is fixed parameter tractable (FPT) with respect to the parameter $$k$$. See this paper of Fomin and Golovach, and the references therein.

• In the cited paper I read that it is concerned with packing a graph with "a maximal set of disjoint cycles". My question doesn't ask for finding a set of maximal cardinality, but for a set whose elements have the highest weightsum; that difference may imply a different algorithmic complexity, depending on the weights. Mar 21, 2020 at 16:25
• You are correct. I edited my answer accordingly to the correct reference. Mar 21, 2020 at 17:01