A fast approximation algorithm for the maximum 2-packing set problem on planar graphs

Given an undirected graph G = (V, E), a subset S subset of V is a 2-packing set if, for any pair of vertices u, v is an element of S, the shortest path between them is at least three-edge long. Finding a 2-packing set of maximum cardinality is an NP-hard problem for arbitrary graphs. This paper proposes an approximation algorithm for the maximum 2-packing set problem for planar graphs. We show that our algorithm is at least lambda-2/lambda of the optimal (i.e. the approximation ratio is lambda/lambda-2), where lambda is a constant related to how the proposed algorithm decomposes the input graph into smaller subgraphs. Then, we improve the solution given by our approximation algorithm by adding some vertices to the solution. Experimentally, we show that our improved algorithm computes a near-optimal 2-packing set. This algorithm is the first approximation algorithm for the maximum 2-packing set to the best of our knowledge.

Automated summary

This paper proposes an approximation algorithm for the maximum 2-packing set problem for planar graphs. By decomposing the graph into smaller subgraphs and improving the solution by adding some vertices, the algorithm computes a near-optimal 2-packing set.