APPROXIMATION ALGORITHMS FOR PSPACE-HARD HIERARCHICALLY AND PERIODICALLY SPECIFIED PROBLEMS

We study the efficient approximability of basic graph and logic proble ms in the literature when instances are specified hierarchically as in [T. Lengauer, J. Assoc. Comput. Mach., 36(1989), pp. 474-509] or are specified by one-dimensional finite narrow periodic specifications as in [E. Wanke, Paths and cycles in finite periodic graphs, in Lecture N otes in Comp. Sci. 711, Springer-Verlag, New York, 1993, pp. 751-760]. We show that, for most of the problems Pi considered when specified u sing k-level-restricted hierarchical specifications or k-narrow period ic specifications, the following hold. (i) Let p be any performance gu arantee of a polynomial time approximation algorithm for Pi, when inst ances are specified using standard specifications. Then For All epsilo n > 0, Pi has a polynomial time approximation algorithm with performan ce guarantee (1 + epsilon)p. (ii) Pi has a polynomial time approximati on scheme when restricted to planar instances. These are the first pol ynomial time approximation schemes for PSPACE-hard hierarchically or p eriodically specified problems. Since several of the problems consider ed are PSPACE-hard, our results provide the first examples of natural PSPACE-hard optimization problems that have polynomial time approximat ion schemes. This answers an open question in Condon et al. [Chicago J . Theoret. Comput. Sci., 1995, Article 4].