Hierarchically specified unit disk graphs

We characterize the complexity of a number of basic optimization problems for unit disk graphs specified hierarchically as in [2, 17, 19, 20]. Both PSPACE-hardness results and polynomial time approximations are presented for most of the problems considered. These problems include minimum vertex coloring, maximum independent set, minimum clique cover, minimum dominating set and minimum independent dominating set. Each of our PSPACE-hardness results holds, when the hierarchical specifications are 1-level restricted and the graphs are specified hierarchically either as in [2] or as in [19]. The hardness results presented here significantly extend the hardness results in [2, 19]. The approximation algorithms presented here along with our results in [24, 25] are among the first polynomial time approximation algorithms for natural PSPACE-hard functions.

Authors

• Madhav V. Marathe Computer Science Dept., University of Virginia Biocomplexity Institute, University of Virginia
• Venkatesh Radhakrishnan
• Harry B. Hunt
• S.S. Ravi

Keywords

No keywords are indexed for this paper.