Approximation Algorithms for NP-Complete Problems on Planar Graphs (Preliminary Version)

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.

Authors

• Brenda S. Baker

Keywords

• Approximation algorithms
• NP-complete problem
• Polynomials
• Dynamic programming
• Minimization methods
• Laboratories
• Partitioning algorithms
• Tiles
• Heart
• Particle separators
• Estimation Algorithm
• Planar Graphs
• Running Time
• Cardinality
• Independent Set
• Positive Integer
• Estimation Strategy
• Linear Time
• Interesting Problem
• Minimum Coverage
• Maximization Problem
• Linear Algorithm
• Polynomial-time Algorithm
• Maximum Independent Set
• Class Of Graphs
• Vertex Cover
• Linear-time Algorithm
• Hamiltonian Path
• Subtree
• Incident Edges
• Counterclockwise
• Cut-points