BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-84-1014
       ENTRY:: May 27, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: A P-complete problem and approximations to it
        TYPE:: Technical Report
      AUTHOR:: Anderson, Richard
      AUTHOR:: Mayr, Ernst W.
        DATE:: September 1984
       PAGES:: 26
    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.
       NOTES:: [Adminitrivia V1/Prg/19950527]
         END:: STAN//CS-TR-84-1014