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?
Asked
Viewed
41 times
1
$\begingroup$
$\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
