On PTAS for planar graph problems

Abstract

Approximation algorithms for a class of planar graph problems, including planar independent set, planar vertex cover and planar dominating set, were intensively studied. The current upper bound on the running time of the polynomial time approximation schemes (PTAS) for these planar graph problems is of 2^{O(1/∈ )}n^O(1). Here we study the lower bound on the running time of the PTAS for these planar graph problems. We prove that there is no PTAS of time 2^{=(√(1/∈ )}n^O(1) for planar independent set, planar vertex cover and planar dominating set unless an unlikely collapse occurs in parameterized complexity theory. For the gap between our lower bound and the current known upper bound, we speci cally show that to further improve the upper bound on the running time of the PTAS for planar vertex cover, we can concentrate on planar vertex cover on pla- nar graphs of degree bounded by three.