I'm looking for a optimization problem on planar graphs which is APX-hard, which means that it doesn't admit a PTAS (approximation scheme). It would be even better is the difficulty of the problem does not depend on some weight value but only on the structure of the graph (because in this case it's probably possible to find such an inapproximability result).

For instance, the following problems all admits a PTAS on planar graphs : - Maximum independent set - Steiner Tree - (Connected) dominating set - Vertex cover - Travelling salesman - k-center/ k-medians - ...

By the way, there are a lot of technique to find PTAS on planar graphs, such as Baker's technique and Arora's technique.

  • 1
    $\begingroup$ www-math.mit.edu/%7Ehajiagha/pcndplanar.pdf $\endgroup$ – D.W. Mar 30 '18 at 5:14
  • 1
    $\begingroup$ According to Demaine and Hajiaghayi, it is open for whether subset feedback vertex set has PTAS. More interestingly, the paper asked whether we have general rule to have PTAS for any planar graph!! This would be big result! erikdemaine.org/papers/PlanarApprox_Encyclopedia2008/paper.pdf $\endgroup$ – YOUSEFY Mar 31 '18 at 9:28
  • $\begingroup$ In the paper of Bateni et al suggested by D.W., they prove that Prize-Collecting Steiner Forest in planar graphs (even in series-parrallel graphs) is APX-hard. The fact is that is this problem we are given a planar graph but also a set of pairs of vertices. There's no restriction about what pairs we can choose or not. The difficulty of this problem is in fact due to "structure" of this set of pair which is not "planar". In contrast, Prize-Collecting Steiner Tree admits a PTAS on planar graphs. $\endgroup$ – Mathieu Mari Jun 18 '18 at 15:29

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.