Refining Approximation Algorithms on Planar Graphs

Abstract

A result by Marx shows that there does not exist a PTAS for Maximum Independent Set on planar graphs running in 2^{O(1/ε)^{1-δ}}n^{O(1)} time, for any δ > 0, assuming ETH holds. We refine this result by showing that the same problem does not admit a PTAS running in 2^{o(1/ε)}n^{O(1)} time, assuming Gap-ETH holds. This refined lower bound is tight in the sense that it matches the running time of the best known PTAS for Maximum Independent Set on planar graphs by Baker in its reliance on ε. We observe that this does not exclude an algorithm that yields (1-ε)-approximations for only specific values of ε in 2^{o(1/ε)}n^{O(1)} time, and expand upon this observation to show the exact algorithm for Maximum Independent Set on planar graphs is optimal for ε ≤ O(1/√n). Additionally, we present polynomial-space PTAS's for the planar versions of Maximum Independent Set, Maximum Weighted Independent Set, Minimum Dominating Set, and Minimum Vertex Cover.