Geodesic
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

Voir la notice de l'article provenant de la source Numdam

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.

DOI : 10.1051/ita:2005041
Classification : 68Q15, 68Q17
Keywords: 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},
     mrnumber = {2197284},
     zbl = {1085.68056},
     language = {en},
     url = {http://geodesic.mathdoc.fr/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
SP  - 75
EP  - 91
VL  - 40
IS  - 1
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita:2005041/
DO  - 10.1051/ita:2005041
LA  - en
ID  - ITA_2006__40_1_75_0
ER  - 
%0 Journal Article
%A Hemaspaandra, Edith
%A Rothe, Jörg
%A Spakowski, Holger
%T Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2006
%P 75-91
%V 40
%N 1
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita:2005041/
%R 10.1051/ita:2005041
%G en
%F ITA_2006__40_1_75_0
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

Cité par Sources :