Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP

Details Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP

2001-10-10

arxiv.org/abs/cs/0110025v2

Computer Science

Computational Complexity

16 pages, 2 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-712294