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

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.