2
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Manfred Weis
    Commented Mar 21, 2020 at 16:25
  • $\begingroup$ You are correct. I edited my answer accordingly to the correct reference. $\endgroup$
    – Tony Huynh
    Commented Mar 21, 2020 at 17:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .