The parallel complexity of the subgraph connectivity problem

It is shown that the problem of testing whether a graph G contains a vertex- (edge-) connected induced subgraph of cardinality k is P-complete for any fixed k⩾3. Moreover, it is shown that approximating within a factor c>1/2 the maximum d for which there is a d-vertex-(d-edge-) connected induced subgraph of G is not in NC, unless P=NC. In contrast, it is known that the problem of finding the Tutte (triconnected) components of G is in NC. On the positive side, it is shown by proving extremal-graph results, that the maximum d for which there is a d-edge-connected induced subgraph of G can be approximated in NC within any factor c<1/2 and that the same is true for vertex connectivity for any C<1/4