Approximation Algorithms for NP-Complete Problems on Planar Graphs

Approximation Algorithms for NP-Complete Problems on Planar Graphs

January 1994 | BRENDA S. BAKER
This paper introduces a general technique for obtaining approximation schemes for various NP-complete problems on planar graphs. The approach involves decomposing a planar graph into subgraphs, called $k$-outerplanar graphs, which can be solved optimally in linear time using dynamic programming. For general planar graphs, the technique provides linear-time algorithms that produce solutions for maximization problems (e.g., maximum independent set) that are at least $k/(k+1)$ optimal, and for minimization problems (e.g., minimum vertex cover) that are at most $(k+1)/k$ optimal. By choosing $k = \lceil c \log \log n \rceil$ or $k = \lceil c \log n \rceil$, where $n$ is the number of nodes, the algorithms become polynomial-time and their solution sizes converge to optimal as $n$ increases. The technique is applicable to problems such as maximum independent set, maximum tile salvage, partition into triangles, maximum H-matching, minimum vertex cover, minimum dominating set, and minimum edge dominating set. The paper also discusses the adaptability of $k$-outerplanar graphs to dynamic programming and provides a detailed algorithm for computing maximum independent sets in outerplanar graphs.This paper introduces a general technique for obtaining approximation schemes for various NP-complete problems on planar graphs. The approach involves decomposing a planar graph into subgraphs, called $k$-outerplanar graphs, which can be solved optimally in linear time using dynamic programming. For general planar graphs, the technique provides linear-time algorithms that produce solutions for maximization problems (e.g., maximum independent set) that are at least $k/(k+1)$ optimal, and for minimization problems (e.g., minimum vertex cover) that are at most $(k+1)/k$ optimal. By choosing $k = \lceil c \log \log n \rceil$ or $k = \lceil c \log n \rceil$, where $n$ is the number of nodes, the algorithms become polynomial-time and their solution sizes converge to optimal as $n$ increases. The technique is applicable to problems such as maximum independent set, maximum tile salvage, partition into triangles, maximum H-matching, minimum vertex cover, minimum dominating set, and minimum edge dominating set. The paper also discusses the adaptability of $k$-outerplanar graphs to dynamic programming and provides a detailed algorithm for computing maximum independent sets in outerplanar graphs.
Reach us at info@study.space