1
$\begingroup$

I have an NP-hard problem which I'm not going to tell you, and I suspect it becomes easier on planar graphs. I tried method Baker but it did not work because we have a restriction on vertices that avoid us to solve the problem in part of the graph then calculate the union of the solution in each part. Also, we try bidimensionality and Klein method but they didn't work because our problem is not contraction closed. Are there any general methodologies for approximation algorithms [or algorithms in general] in planar graphs beyond bidimensionality and Klein's method, for example when a problem is not contraction closed?

$\endgroup$
  • $\begingroup$ I think you mean contraction rather than contradiction. $\endgroup$ – Yuval Filmus Nov 17 '17 at 21:02
  • 2
    $\begingroup$ You should probably rephrase your question. At the moment it reads: "I have this NP-hard problem which I'm not going to tell you, and I suspect it becomes easier on planar graphs. I tried methods X and Y but they didn't work. Help???", whereas it should read: "Are there any general methodologies for approximation algorithms [or algorithms in general] in planar graphs beyond bidimensionality and Klein's method?" $\endgroup$ – Yuval Filmus Nov 17 '17 at 21:05

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.