Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP
✍ Scribed by Edith Hemaspaandra; Jörg Rothe
- Publisher
- Elsevier Science
- Year
- 1998
- Tongue
- English
- Weight
- 511 KB
- Volume
- 65
- Category
- Article
- ISSN
- 0020-0190
No coin nor oath required. For personal study only.
✦ Synopsis
investigate the computational complexity of the problem of whether the Minimum Degree Greedy Algorithm can approximate a maximum independent set of a graph within a constant factor of r, for fixed rational r > 1. They denote this problem by S, and prove that for each rational r 2 1, S, is coNP-hard. They also provide a PNP upper bound of S,, leaving open the question of whether this gap between the upper and the lower bound of S, can be closed. For the special case of r = 1, they show that SI is even DP-hard, again leaving open the question of whether S1 can be shown to be complete for DP or some larger class such as PNP. In this note, we completely solve all the questions left open by Bodlaender et al. Our main result is that for each rational r 2 1, S, is complete for Pf;', the class of sets solvable via parallel access to NP. @