RECOGNIZING WHEN GREED CAN APPROXIMATE MAXIMUM INDEPENDENT SETS IS COMPLETE FOR PARALLEL ACCESS TO NP

Bodlaender, Thilikos, and Yamazaki (1997) investigate the computationa l complexity of the problem of whether the Minimum Degree Greedy Algor ithm can approximate a maximum independent set of a graph within a con stant factor of r, for fixed rational r greater than or equal to 1. Th ey denote this problem by S-r and prove that for each rational r great er than or equal to 1, S-r is coNP-hard. They also provide a P-NP uppe r bound of S-r, leaving open the question of whether this gap between the upper and the lower bound of S-r can be closed. For the special ca se of r = 1, they show that S-1 is even DP-hard, again leaving open th e question of whether S-1 can be shown to be complete for DP or some l arger class such as P-NP. In this note, we completely solve all the qu estions left open by Bodlaender et al. Our main result is that for eac h rational r greater than or equal to 1, S-r is complete for p(paralle l to)(NP), the class of sets solvable via parallel access to NP. (C) 1 998 Elsevier Science B.V.