Abstract
We extend the concept of polynomial time approximation algorithms to apply to problems for hierarchically specified graphs, many of which are PSPACE-complete. Assuming P ≠ PSPACE, the existence or nonexistence of such efficient approximation algorithms is characterized, for several standard graph theoretic and combinatorial problems. We present polynomial time approximation algorithms for several standard problems considered in the literature. In contrast, we show that unless P = PSPACE, there is no polynomial time ε-approximation for any ε > 0, for several other problems, when the instances are specified hierarchically.
Research supported in part by NSF Grants CCR 89-03319 and CCR 89-05296.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
R.J. Anderson and E.W. Mayr “Approximating P-complete problems,” Tech Report, Stanford University, 1986.
J.L. Bentley, T. Ottmann, P. Widmayer, “The Complexity of Manipulating Hierarchically Defined set of Intervals,” Advances in Computing Research, ed. F.P. Preparata Vol. 1, (1983), pp. 127–158.
A. Condon, J. Feigenbaum, C. Lund and P. Shor, “Probabilistically Checkable Debate Systems and Approximation Algorithms for PSPACE-Hard Functions”, to appear in Proc. 25th ACM Symposium on Theory of Computing, 1993.
H. Galperin and A. Wigderson, “Succinct Representation of Graphs,” Information and Control, Vol. 56, 1983, pp. 183–198.
M.R. Garey, D.S. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness, Freeman, San Francisco CA, 1979.
F. Höfting, T. Lengauer and E. Wanke, “Processing of Hierarchically Defined Graphs and Graph Families”, in Data Structures and Efficient Algorithms (Final Report on the DFG Special Joint Initiative), LNCS 594, Springer-Verlag, 1992, pp. 44–69.
H.B. Hunt III, V. Radhakrishnan, R.E. Stearns, “On The Complexity of Generalized Satisfiability and Hierarchically Specified Generalized Satisfiability Problems,” in preparation.
R.M. Karp, A. Wigderson, “A Fast Parallel Algorithm for the Maximal Independent Set Problem”, J.ACM, Vol. 32, No.4, July 1985, pp. 762–773.
L. Kirousis, M. Serna and P. Spirakis, “The Parallel Complexity of the Subgraph Connectivity problem,” Proc. 30th IEEE-FOCS, 1989, pp. 294–299
T. Lengauer and C. Weiner, “Efficient Solutions hierarchical systems of linear equations,” Computing, Vol 39, 1987, pp. 111–132.
T. Lengauer, K.W. Wagner, “The correlation between the complexities of non-hierarchical and hierarchical versions of graph problems”, JCSS, Vol. 44 1992, pp. 63–93.
T. Lengauer, “Hierarchical Planarity Testing,” J.ACM, Vol. 36, No.3, July 1989, pp. 474–509.
T. Lengauer, “Efficient Solutions for Connectivity Problems for Hierarchically Defined Graphs,” SIAM J. Computing, Vol. 17, No. 6, 1988, pp. 1063–1080.
T. Lengauer, “Efficient Algorithms for Finding Minimum Spanning Forests of Hierarchically Defined graphs,” Journal of Algorithms, Vol. 8, 1987, pp. 260–284.
T. Lengauer, “Exploiting Hierarchy in VLSI Design,” Proc. AWOC '86, LNCS 227, Springer-Verlag, 1986, pp. 180–193.
M. Serna, “Approximating Linear Programming is log-space complete for P,” Inf. Proc. Letters, Vol. 37, No. 4, 1991, pp. 233–236.
G. Pantziou, P. Spirakis, C. Zaroliagis, “Fast Parallel Approximations of the Maximum Weighted Cut Problem Through Derandomization,” Proc. 9 th Foundations of Software Technology and Theoretical Computer Science, FCT-TCS, 1989, pp. 20–29.
K.W. Wagner, “The complexity of Combinatorial Problems with Succinct Input Representation,” Acta Informatica, Vol. 23, No.3, 1986, pp. 325–356.
M. Williams, “Efficient Processing of Hierarchical Graphs,” TR 90-06, Dept of Computer Science, Iowa Sate University. (Parts of the report appeared in WADS'89 and SWAT'90 coauthored with F. Baca.)
M. Yannakakis, “On the Approximation of Maximum Satisfiability,” Proc. Third Annual ACM-SIAM Symp. on Discrete Algorithms, Jan. 1992, pp 1–9.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Marathe, M.V., Hunt, H.B., Ravi, S.S. (1993). The complexity of approximating PSPACE-complete problems for hierarchical specifications. In: Lingas, A., Karlsson, R., Carlsson, S. (eds) Automata, Languages and Programming. ICALP 1993. Lecture Notes in Computer Science, vol 700. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56939-1_63
Download citation
DOI: https://doi.org/10.1007/3-540-56939-1_63
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56939-8
Online ISBN: 978-3-540-47826-3
eBook Packages: Springer Book Archive