AbstractWe extend the concept of polynomial time approximation algorithms to apply to problems for hierarchically specified graphs, many of which are PSPACE-complete. We present polynomial time approximation algorithms for several standard PSPACE-hard problems considered in the literature. In contrast, we prove that finding epsilon-approximations for any epsilon > 0, for several other problems when the instances are specified hierarchically, is PSPACE-hard. We present polynomial time approximation algorithms for the following problems when the graphs are specified hierarchically: minimum vertex cover, maximum 3SAT, weighted max cut, minimum maximal matching, and bounded degree maximum independent set.
In contrast, we show that for any epsilon > 0, obtaining epsilon-approximations for the following problems when the instances are specified hierarchically is PSPACE-hard: the number of true gates in a monotone acyclic circuit when all input values are specified and the optimal value of the objective function of a linear program.
It is also shown that obtaining a performance guarantee of less than 2 is PSPACE-hard for the following problems when the instances are specified hierarchically: high degree subgraph, k-vertex connected subgraph and k-edge connected subgraph.
Additional Key Words and Phrases: hierarchical specifications, approximation algorithms, computational complexity, algorithms and data structures
Selected papers that cite this one
- Anne Condon, Joan Feinberg, Carsten Lund, and Peter Shor. Random debaters and the hardness of approximating stochastic functions. SIAM Journal on Computing, 26(2):369-400, April 1997.
- Harry B. Hunt III, Madhav V. Marathe, Venkatesh Radhakrishnan, S. S. Ravi, Daniel J. Rosenkrantz, and Richard E. Stearns. NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. Journal of Algorithms, 26(2):238-274, February 1998.
- Madhav V. Marathe, Harry B. Hunt III, Richard E. Stearns, and Venkatesh Radhakrishnan. Approximation algorithms for PSPACE-hard hierarchically and periodically specified problems. SIAM Journal on Computing, 27(5):1237-1261, October 1998.
Selected references
- Anne Condon, Joan Feigenbaum, Carsten Lund, and Peter Shor. Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions (extended abstract). In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 305-314, San Diego, California, 16-18 May 1993.
- Richard M. Karp and Avi Wigderson. A fast parallel algorithm for the maximal independent set problem. Journal of the ACM, 32(4):762-773, October 1985.
- Thomas Lengauer. The complexity of compacting hierarchically specified layouts of integrated circuits (preliminary version). In 23rd Annual Symposium on Foundations of Computer Science, pages 358-368, Chicago, Illinois, 3-5 November 1982. IEEE.
- Thomas Lengauer. Hierarchical planarity testing algorithms. Journal of the ACM, 36(3):474-509, July 1989.
- Thomas Lengauer and Egon Wanke. Efficient decision procedures for graph properties on context-free graph languages. Journal of the ACM, 40(2):368-393, April 1993.
- M. V. Marathe, H. B. Hunt III, R. E. Stearns, and V. Radhakrishnan. Approximation schemes for PSPACE-complete problems for succint specifications (preliminary version). In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 468-477, Montréal, Québec, Canada, 23-25 May 1994.
- Klaus W. Wagner. The complexity of combinatorial problems with succinct input representation. Acta Informatica, 23(3):325-356, 1986.