0
$\begingroup$

What is the best approximation for odd cycle transversal? (on general graphs) Sorry if this is easily found everything I found about odd cycles is about paramaterized complexity and kernels

Improve this question
$\endgroup$
4
  • $\begingroup$ if you're looking for an approximation, what level of precision are you seeking? $\endgroup$
    – Zach Hunter
    Aug 20, 2019 at 21:58
  • $\begingroup$ I'm looking for an approximation algorithm for odd cycle transversal on general graphs $\endgroup$
    – Hao S
    Aug 20, 2019 at 22:04
  • $\begingroup$ yes, but what does it mean to approximate odd-cycle traversal, and what level of approximation is sufficient? $\endgroup$
    – Zach Hunter
    Aug 20, 2019 at 22:06
  • $\begingroup$ @ZacharyHunter I mean return an odd cycle transversal of cost at most a*OPT where OPT is the smallest cost of a solution en.wikipedia.org/wiki/… p.s. why does it not allow me to change the tag from approximation to approximation algorithm?? I want to change the tag as I realize it's the wrong tag $\endgroup$
    – Hao S
    Aug 20, 2019 at 22:23

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.