Report Number: CS-TR-84-1014
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