THE PARALLEL COMPLEXITY OF APPROXIMATING THE HIGH-DEGREE SUBGRAPH PROBLEM

The HIGH DEGREE SUBGRAPH problem is to find a subgraph H of a graph G such that the minimum degree of H is as large as possible. This proble m is known to be P-hard so that parallel approximation algorithms are very important for it. Our first goal is to determine how effectively the approximation algorithm based on a well-known extremal graph resul t parallelizes. In particular, we show that two natural decision probl ems associated with this algorithm are P-complete: these results sugge st that the parallel implementation of the algorithm itself requires m ore sophisticated techniques. Successively, we study the HIGH DEGREE S UBGRAPH problem for random graphs with any edge probability function a nd we provide different parallel approximation algorithms depending on the type of this function. (C) 1998-Elsevier Science B.V. All rights reserved.