Hostname: page-component-78c5997874-v9fdk Total loading time: 0 Render date: 2024-11-14T11:16:46.620Z Has data issue: false hasContentIssue false
  • English
  • Français

Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP

Published online by Cambridge University Press:  15 October 2005

Edith Hemaspaandra ,
Jörg Rothe  and
Holger Spakowski
Edith Hemaspaandra
Affiliation:
Department of Computer Science, Rochester Institute of Technology, Rochester, NY 14623, USA; [email protected]
Jörg Rothe
Affiliation:
Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, 40225 Düsseldorf, Germany; [email protected]; [email protected]
Holger Spakowski
Affiliation:
Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, 40225 Düsseldorf, Germany; [email protected]; [email protected]
Get access

Abstract

For both the edge deletion heuristic and the maximum-degree greedy heuristic, we studythe problem of recognizing those graphs for which that heuristic can approximate the size of a minimum vertex cover within a constant factor of r, where r is a fixed rational number. Our main results are that these problems are complete for the class of problems solvable via parallel access to NP. To achieve these main results, we also show that the restriction of the vertex cover problem to those graphs for which either of these heuristics can find an optimal solution remains NP-hard.

Keywords

Computational complexitycompletenessminimum vertex cover heuristicsapproximationparallel access to NP
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 40 , Issue 1 , January 2006 , pp. 75 - 91
Copyright
© EDP Sciences, 2006

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Bodlaender, H., Thilikos, D. and Yamazaki, K., It is hard to know when greedy is good for finding independent sets. Inform. Process. Lett. 61 (1997) 101–106. CrossRef
Chvátal, V., A greedy heuristic for the set-covering problem. Math. Oper. Res. 4 (1979) 233–235. CrossRef
Eiter, T. and Gottlob, G., The complexity class $\Theta^{p}_{2}$ : Recent results and applications, in Proc. of the 11th Conference on Fundamentals of Computation Theory. Lect. Notes Comput. Sci. 1279 (1997) 1–18. CrossRef
Feige, U., A threshold of lnn for approximating set cover. J. ACM 45 (1998) 634–652. CrossRef
M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979).
R. Graham, D. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley (1989).
Hemachandra, L., The strong exponential hierarchy collapses. J. Comput. Syst. Sci. 39 (1989) 299–322. CrossRef
Hemaspaandra, E. and Hemaspaandra, L., Computational politics: Electoral systems, in Proc. of the 25th International Symposium on Mathematical Foundations of Computer Science. Lect. Notes Comput. Sci. 1893 (2000) 64–83. CrossRef
Hemaspaandra, E., Hemaspaandra, L. and Rothe, J., Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP. J. ACM 44 (1997) 806–825. CrossRef
Hemaspaandra, E., Hemaspaandra, L. and Rothe, J., Raising NP lower bounds to parallel NP lower bounds. SIGACT News 28 (1997) 2–13.
Hemaspaandra, E. and Rothe, J., Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP. Inform. Proc. Lett. 65 (1998) 151–156. CrossRef
E. Hemaspaandra, H. Spakowski and J. Vogel, The complexity of Kemeny elections. Theor. Comput. Sci. Accepted subject to minor revision.
Hemaspaandra, E. and Wechsung, G., The minimization problem for boolean formulas. SIAM J. Comput. 31 (2002) 1948–1958. CrossRef
Johnson, D., Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9 (1974) 256–278. CrossRef
Kadin, J., PNP[log n] and sparse Turing-complete sets for NP. J. Comput. Syst. Sci. 39 (1989) 282–298. CrossRef
Krentel, M., The complexity of optimization problems. J. Comput. Syst. Sci. 36 (1988) 490–509. CrossRef
Köbler, J., Schöning, U. and Wagner, K., The difference and truth-table hierarchies for NP. RAIRO-Inf. Theor. Appl. 21 (1987) 419–435. CrossRef
Lovász, L., On the ratio of optimal integral and fractional covers. Discrete Math. 13 (1975) 383–390. CrossRef
Lund, C. and Yannakakis, M., On the hardness of approximating minimization problems. J. ACM 41 (1994) 960–981. CrossRef
C. Papadimitriou, Computational Complexity. Addison-Wesley (1994).
C. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall (1982).
Papadimitriou, C. and Zachos, S., Two remarks on the power of counting, in Proc. of the 6th GI Conference on Theoretical Computer Science. Lect. Notes Comput. Sci. 145 (1983) 269–276. CrossRef
T. Riege and J. Rothe, Complexity of the exact domatic number problem and of the exact conveyor flow shop problem. Theory of Computing Systems (2004). On-line publication DOI 10.1007/s00224-004-1209-8. Paper publication to appear.
Rothe, J., Spakowski, H. and Vogel, J., Exact complexity of the winner problem for Young elections. Theory Comput. Syst. 36 (2003) 375–386. CrossRef
Spakowski, H. and Vogel, J., $\Theta_{2}^{p}$ -completeness: A classical approach for new results, in Proc. of the 20th Conference on Foundations of Software Technology and Theoretical Computer Science. Lect. Notes Comput. Sci. 1974 (2000) 348–360. CrossRef
Wagner, K., More complicated questions about maxima and minima, and some closures of NP. Theor. Comput. Sci. 51 (1987) 53–80. CrossRef
Wagner, K., Bounded query classes. SIAM J. Comput. 19 (1990) 833–846. CrossRef