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

  • $\begingroup$ if you're looking for an approximation, what level of precision are you seeking? $\endgroup$ – Zachary Hunter Aug 20 '19 at 21:58
  • $\begingroup$ I'm looking for an approximation algorithm for odd cycle transversal on general graphs $\endgroup$ – Hao S Aug 20 '19 at 22:04
  • $\begingroup$ yes, but what does it mean to approximate odd-cycle traversal, and what level of approximation is sufficient? $\endgroup$ – Zachary Hunter Aug 20 '19 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 '19 at 22:23

Your Answer

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

Browse other questions tagged or ask your own question.