Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NPEdith Hemaspaandra, Jörg Rothe and Holger SpakowskiRAIRO-Theor. Inf. Appl., 40 1 (2006) 75-91DOI: https://doi.org/10.1051/ita:2005041
