On PTAS for Planar Graph Problems Academic Article uri icon

abstract

  • Approximation algorithms for a class of planar graph problems, including Planar Independent Set, Planar Vertex Cover and Poanar 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 2O(1/∈)nO(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 2o(√1/∈)nO(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 specifically 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 planar graphs of degree bounded by three. © 2006 International Federation for Information Processing.

author list (cited authors)

  • Huang, X., & Chen, J.

publication date

  • January 1, 2006 11:11 AM