Skip to main content
deleted 97 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

The problem is NP-hard, even in the unweighted case (all weights equal to $1$). There is Indeed, given a polynomial-timegraph $O(\sqrt {\log n)}$-approximation algorithm due to Krivelevich, Nutov, Salavatipour, Verstraete,$G$ and Yusteran integer $k$, wheredeciding if $n$$G$ contains an Eulerian subgraph with at least $k$ edges is the number of vertices of the graphNP-complete. This approximation ratio However, the problem is essentially best possiblefixed parameter tractable (under a natural complexity class assumptionFPT) with respect to the parameter $k$. See this paperpaper of FriggstadFomin and Salavatipour for allGolovach, and the aforementioned resultsreferences therein.

The problem is NP-hard, even in the unweighted case (all weights equal to $1$). There is a polynomial-time $O(\sqrt {\log n)}$-approximation algorithm due to Krivelevich, Nutov, Salavatipour, Verstraete, and Yuster, where $n$ is the number of vertices of the graph. This approximation ratio is essentially best possible (under a natural complexity class assumption). See this paper of Friggstad and Salavatipour for all the aforementioned results.

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.

Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

The problem is NP-hard, even in the unweighted case (all weights equal to $1$). There is a polynomial-time $O(\sqrt {\log n)}$-approximation algorithm due to Krivelevich, Nutov, Salavatipour, Verstraete, and Yuster, where $n$ is the number of vertices of the graph. This approximation ratio is essentially best possible (under a natural complexity class assumption). See this paper of Friggstad and Salavatipour for all the aforementioned results.