| Issue |
RAIRO-Theor. Inf. Appl.
Volume 40, Number 1, January-March 2006
|
|
|---|---|---|
| Page(s) | 75 - 91 | |
| DOI | https://doi.org/10.1051/ita:2005041 | |
| Published online | 15 October 2005 | |
Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
1
Department of Computer Science,
Rochester Institute of Technology,
Rochester, NY 14623, USA;
eh@cs.rit.edu
2
Institut für Informatik,
Heinrich-Heine-Universität Düsseldorf,
40225 Düsseldorf, Germany;
rothe@cs.uni-duesseldorf.de; spakowsk@cs.uni-duesseldorf.de
Received:
July
2004
Accepted:
10
February
2005
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.
Mathematics Subject Classification: 68Q15 / 68Q17
Key words: Computational complexity / completeness / minimum vertex cover heuristics / approximation / parallel access to NP
© EDP Sciences, 2006
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.