Approximation algorithms for maximum independent set of a unit disk graph

• A 2-factor approximation for computing the maximum independent set of unit disk graph is proposed. It runs in O(n3)O(n3) time and O(n2)O(n2) space.
• A similar technique works for penny graph in O(nlog⁡n)O(nlog⁡n) time and produces a 2-approximation result.
• Efficient PTAS are proposed for computing the maximum independent set of unit disk graph and penny graph.

We propose a 2-approximation algorithm for the maximum independent set problem for a unit disk graph. The time and space complexities are O(n3)O(n3) and O(n2)O(n2), respectively. For a penny graph, our proposed 2-approximation algorithm works in O(nlog⁡n)O(nlog⁡n) time using O(n)O(n) space. We also propose a polynomial-time approximation scheme (PTAS) for the maximum independent set problem for a unit disk graph. Given an integer k>1k>1, it produces a solution of size 1(1+1k)2|OPT| in O(k4nσklog⁡k+nlog⁡n)O(k4nσklog⁡k+nlog⁡n) time and O(n+klog⁡k)O(n+klog⁡k) space, where OPT   is the subset of disks in an optimal solution and σk≤7k3+2. For a penny graph, the proposed PTAS produces a solution of size 1(1+1k)|OPT| in O(22σknk+nlog⁡n)O(22σknk+nlog⁡n) time using O(2σk+n)O(2σk+n) space.