HIERARCHICALLY SPECIFIED UNIT DISK GRAPHS

We characterize the complexity of a number of basic optimization probl ems 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 cove r, minimum dominating set and minimum independent dominating set. Each of our PSPACE-hardness results holds, when the hierarchical specifica tions are 1-level restricted and the graphs are specified hierarchical ly either as in [2] or as in [19]. The hardness results presented here significantly extend the hardness results in [2, 19]. The approximati on algorithms presented here along with our results in [24, 25] are am ong the first polynomial time approximation algorithms for natural PSP ACE-hard functions.