A P-complete problem and approximations to it
Richard G. Anderson, Ernst W Mayr · 1984
The P-complete problem that we will consider is the High Degree Subgraph Problem. This problem is: given a graph G = (V,E) and an integer k, find the maximum induced subgraph of G that has all nodes of degree at least k. After showing that this problem is P-complete, we will discuss two approaches to finding approximate solutions to it in NC. We will give a variant of the problem that is also P-complete that can be approximated to within a factor of c in NC, for any c > 1/2, but cannot be approximated by a factor of better than 1/2 unless P = NC. We will also give an algorithm that finds a subgraph with moderately high minimum degree. This algorithm exhibits an interesting relationship between its performance and the time it takes.