On efficient polynomial-time approximation schemes for problems on planar structures
Liming Cai, Michael R. Fellows, David W. Juedes, Frances Rosamond · 2009
This work examines the existence of efficient polynomial-time approximation schemes (EPTAS) for a variety of problems contained in the syntactic classes Planar TMIN, Planar TMAX, and Planar MPSAT as defined by Khanna and Motwani. Based on the recent work of Alber, Bodlaender, Fernau and Niedermeier and others, we describe subclasses of problems from Planar TMIN, Planar TMAX, and Planar MPSAT that have EPTAS. In contrast, we show that there exist W[1]-hard problems in Planar TMIN, Planar TMAX, and Planar MPSAT. It follows that these problems do not have efficient polynomial-time approximation schemes, unless W[1]=FPT. As our main result, we show that the existence of efficient polynomial-time approximation schemes for certain problems is closely connected their syntactic complexity: all problems that can be described by a collection of first order formulas with minterms of size 1 have efficient polynomial-time approximation schemes; in contrast, there exist W[1]-hard problems that can be described by collections of first order formula with minterms of size 4. Classification: computational and structural complexity.