Approximation algorithms for NP-complete problems on planar graphs

Abstract

This paper describes a general technique that can be used to obtain approximation algorithms for various NP-complete problems on planar graphs. The strategy depends on decomposing a planar graph into subgraphs of a form we call k- outerplanar. For fixed k, the problems of interest are solvable optimally in linear time on k-outerplanar graphs by dynamic programming. For general planar graphs, if the problem is a maximization problem, such as maximum independent set, this technique gives for each k a linear time algorithm that produces a solution whose size is at least (k-1)/k optimal. If the problem is a minimization problem, such as minimum vertex cover, it gives for each k a linear time algorithm that produces a solution whose size is at most (k + 1)/k optimal. Taking k = c log log n or k = c log n, where n is the number of nodes and c is some constant, we get polynomial time approximation schemes, i.e. algorithms whose solution sizes converge toward optimal as n increases. The class of problems for which this approach provides approximation schemes includes maximum independent set, maximum tile salvage, partition into triangles, maximum H-matching, minimum vertex cover, minimum dominating set, and minimum edge dominating set. For these and certain other problems, the proof of solvability on k-outerplanar graphs also enlarges the class of planar graphs for which the problems are known to be solvable.