Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
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 , where is a fixed rational number. Our main results are that these problems are complete for the class of problems solvable via parallel access to . To achieve these main results, we also show that the restriction of the vertex cover problem to those graphs for which...