Parallel Complexity of the Connected Subgraph Problem
Lefteris M. Kirousis, Marı́a Serna, Paul G. Spirakis · SIAM Journal on Computing · 1993
This paper shows that the problem of testing whether a graph G contains an induced subgraph of vertex (edge) connectivity at least k is P-complete for any fixed $k \geqslant 3$. Moreover, if $k_{\max } $ is the largest vertex (edge) connectivity of any subgraph of G, it is shown that unless ${\text{P}} = {\text{NC}}$ there is no NC algorithm that approximates $k_{\max } $ within any approximation factor $\frac{1}{2} < c < 1$ (such an algorithm is by definition one that outputs a number in the interval $[ck_{\max } ,k_{\max } ]$). In contrast, it is known that the problem of finding the Tutte (triconnected) components of G (i.e., the maximal subgraphs of G such that for any four vertices in any of them, any two of these vertices can be connected by a path in G that avoids the other two) is in NC. On the positive side, it is shown, by proving extremal graph results, that the maximum k for which there is a k-edge-connected induced subgraph of G can be approximated in NC for any approximation factor strictly less than $\frac{1}{2}$ and that the same is true for vertex connectivity for any approximation factor strictly less than $\frac{1}{4}$.