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 problem 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 result parallelizes. In particular, we show that two natural decision problems associated with this algorithm are P-complete: these results suggest that the parallel implementation of the algorithm itself requires more sophisticated techniques. Successively, we study the High degree subgraph problem for random graphs with any edge probability function and we provide different parallel approximation algorithms depending on the type of this function.