Institution: Stanford University, Department of Computer Science

Title: A P-complete problem and approximations to it

Author: Anderson, Richard

Author: Mayr, Ernst W.

Date: September 1984

Abstract: 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.

http://i.stanford.edu/pub/cstr/reports/cs/tr/84/1014/CS-TR-84-1014.pdf