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

Edith Hemaspaandra; Jörg Rothe; Holger Spakowski

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 40, Issue: 1, page 75-91
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topHemaspaandra, Edith, Rothe, Jörg, and Spakowski, Holger. "Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP." RAIRO - Theoretical Informatics and Applications 40.1 (2010): 75-91. <http://eudml.org/doc/92790>.

@article{Hemaspaandra2010,

abstract = {
For both the edge deletion heuristic and the
maximum-degree greedy heuristic, we study
the 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.
},

author = {Hemaspaandra, Edith, Rothe, Jörg, Spakowski, Holger},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Computational complexity; completeness; minimum vertex cover
heuristics; approximation; parallel access to NP},

language = {eng},

month = {3},

number = {1},

pages = {75-91},

publisher = {EDP Sciences},

title = {Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP},

url = {http://eudml.org/doc/92790},

volume = {40},

year = {2010},

}

TY - JOUR

AU - Hemaspaandra, Edith

AU - Rothe, Jörg

AU - Spakowski, Holger

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

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 40

IS - 1

SP - 75

EP - 91

AB -
For both the edge deletion heuristic and the
maximum-degree greedy heuristic, we study
the 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.

LA - eng

KW - Computational complexity; completeness; minimum vertex cover
heuristics; approximation; parallel access to NP

UR - http://eudml.org/doc/92790

ER -

## References

top- H. Bodlaender, D. Thilikos and K. Yamazaki, It is hard to know when greedy is good for finding independent sets. Inform. Process. Lett.61 (1997) 101–106. Zbl1336.68094
- V. Chvátal, A greedy heuristic for the set-covering problem. Math. Oper. Res.4 (1979) 233–235. Zbl0443.90066
- T. Eiter and G. Gottlob, The complexity class ${\Theta}_{2}^{p}$: Recent results and applications, in Proc. of the 11th Conference on Fundamentals of Computation Theory. Lect. Notes Comput. Sci.1279 (1997) 1–18.
- U. Feige, A threshold of lnn for approximating set cover. J. ACM45 (1998) 634–652. Zbl1065.68573
- M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979). Zbl0411.68039
- R. Graham, D. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley (1989).
- L. Hemachandra, The strong exponential hierarchy collapses. J. Comput. Syst. Sci.39 (1989) 299–322. Zbl0693.03022
- E. Hemaspaandra and L. Hemaspaandra, 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. Zbl0996.68065
- E. Hemaspaandra, L. Hemaspaandra and J. Rothe, Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP. J. ACM44 (1997) 806–825. Zbl0904.68111
- E. Hemaspaandra, L. Hemaspaandra and J. Rothe, Raising NP lower bounds to parallel NP lower bounds. SIGACT News28 (1997) 2–13. Zbl0904.68111
- E. Hemaspaandra and J. Rothe, Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP. Inform. Proc. Lett.65 (1998) 151–156. Zbl06590681
- E. Hemaspaandra, H. Spakowski and J. Vogel, The complexity of Kemeny elections. Theor. Comput. Sci. Accepted subject to minor revision. Zbl1086.68046
- E. Hemaspaandra and G. Wechsung, The minimization problem for boolean formulas. SIAM J. Comput.31 (2002) 1948–1958. Zbl1008.68054
- D. Johnson, Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci.9 (1974) 256–278. Zbl0296.65036
- J. Kadin, PNP[log n] and sparse Turing-complete sets for NP. J. Comput. Syst. Sci.39 (1989) 282–298. Zbl0693.68027
- M. Krentel, The complexity of optimization problems. J. Comput. Syst. Sci.36 (1988) 490–509. Zbl0652.68040
- J. Köbler, U. Schöning and K. Wagner, The difference and truth-table hierarchies for NP. RAIRO-Inf. Theor. Appl.21 (1987) 419–435. Zbl0642.03024
- L. Lovász, On the ratio of optimal integral and fractional covers. Discrete Math.13 (1975) 383–390. Zbl0323.05127
- C. Lund and M. Yannakakis, On the hardness of approximating minimization problems. J. ACM41 (1994) 960–981. Zbl0814.68064
- C. Papadimitriou, Computational Complexity. Addison-Wesley (1994).
- C. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall (1982). Zbl0503.90060
- C. Papadimitriou and S. Zachos, 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.
- 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 . Paper publication to appear. Zbl1100.68085DOI10.1007/s00224-004-1209-8
- J. Rothe, H. Spakowski and J. Vogel, Exact complexity of the winner problem for Young elections. Theory Comput. Syst.36 (2003) 375–386. Zbl1061.90084
- H. Spakowski and J. Vogel, ${\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. Zbl1044.68062
- K. Wagner, More complicated questions about maxima and minima, and some closures of NP. Theor. Comput. Sci.51 (1987) 53–80. Zbl0653.03027
- K. Wagner, Bounded query classes. SIAM J. Comput.19 (1990) 833–846. Zbl0711.68047

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.