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.

$\endgroup$

1 Answer 1

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.