Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 1, pp. 75-91.

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 $\text{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.

DOI : https://doi.org/10.1051/ita:2005041
Classification : 68Q15,  68Q17
Mots clés : computational complexity, completeness, minimum vertex cover heuristics, approximation, parallel access to NP
@article{ITA_2006__40_1_75_0,
author = {Hemaspaandra, Edith and Rothe, J\"org and Spakowski, Holger},
title = {Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to {NP}},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {75--91},
publisher = {EDP-Sciences},
volume = {40},
number = {1},
year = {2006},
doi = {10.1051/ita:2005041},
zbl = {1085.68056},
mrnumber = {2197284},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita:2005041/}
}
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 - Informatique Théorique et Applications
PY  - 2006
DA  - 2006///
SP  - 75
EP  - 91
VL  - 40
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2005041/
UR  - https://zbmath.org/?q=an%3A1085.68056
UR  - https://www.ams.org/mathscinet-getitem?mr=2197284
UR  - https://doi.org/10.1051/ita:2005041
DO  - 10.1051/ita:2005041
LA  - en
ID  - ITA_2006__40_1_75_0
ER  - 
Hemaspaandra, Edith; Rothe, Jörg; Spakowski, Holger. Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 1, pp. 75-91. doi : 10.1051/ita:2005041. http://www.numdam.org/articles/10.1051/ita:2005041/

[1] 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.

[2] V. Chvátal, A greedy heuristic for the set-covering problem. Math. Oper. Res. 4 (1979) 233-235. | Zbl 0443.90066

[3] 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.

[4] U. Feige, A threshold of $lnn$ for approximating set cover. J. ACM 45 (1998) 634-652. | Zbl 1065.68573

[5] M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979). | MR 519066 | Zbl 0411.68039

[6] R. Graham, D. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley (1989). | MR 1397498 | Zbl 0668.00003

[7] L. Hemachandra, The strong exponential hierarchy collapses. J. Comput. Syst. Sci. 39 (1989) 299-322. | Zbl 0693.03022

[8] 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. | Zbl 0996.68065

[9] 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. ACM 44 (1997) 806-825. | Zbl 0904.68111

[10] E. Hemaspaandra, L. Hemaspaandra and J. Rothe, Raising NP lower bounds to parallel NP lower bounds. SIGACT News 28 (1997) 2-13.

[11] 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.

[12] E. Hemaspaandra, H. Spakowski and J. Vogel, The complexity of Kemeny elections. Theor. Comput. Sci. Accepted subject to minor revision. | MR 2183163 | Zbl 1086.68046

[13] E. Hemaspaandra and G. Wechsung, The minimization problem for boolean formulas. SIAM J. Comput. 31 (2002) 1948-1958. | Zbl 1008.68054

[14] D. Johnson, Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9 (1974) 256-278. | Zbl 0296.65036

[15] J. Kadin, ${\mathrm{P}}^{\mathrm{N}\mathrm{P}\left[log\mathrm{n}\right]}$ and sparse Turing-complete sets for NP. J. Comput. Syst. Sci. 39 (1989) 282-298. | Zbl 0693.68027

[16] M. Krentel, The complexity of optimization problems. J. Comput. Syst. Sci. 36 (1988) 490-509. | Zbl 0652.68040

[17] 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. | Numdam | Zbl 0642.03024

[18] L. Lovász, On the ratio of optimal integral and fractional covers. Discrete Math. 13 (1975) 383-390. | Zbl 0323.05127

[19] C. Lund and M. Yannakakis, On the hardness of approximating minimization problems. J. ACM 41 (1994) 960-981. | Zbl 0814.68064

[20] C. Papadimitriou, Computational Complexity. Addison-Wesley (1994). | MR 1251285 | Zbl 0833.68049

[21] C. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall (1982). | MR 663728 | Zbl 0503.90060

[22] 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. | Zbl 0506.68039

[23] 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. | MR 2256634 | Zbl 1100.68085

[24] J. Rothe, H. Spakowski and J. Vogel, Exact complexity of the winner problem for Young elections. Theory Comput. Syst. 36 (2003) 375-386. | Zbl 1061.90084

[25] 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. | Zbl 1044.68062

[26] K. Wagner, More complicated questions about maxima and minima, and some closures of NP. Theor. Comput. Sci. 51 (1987) 53-80. | Zbl 0653.03027

[27] K. Wagner, Bounded query classes. SIAM J. Comput. 19 (1990) 833-846. | Zbl 0711.68047

Cité par Sources :