Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
Parallel complexity of the connected subgraph problem
Ist Teil von
SIAM journal on computing, 1993-06, Vol.22 (3), p.573-586
Ort / Verlag
Philadelphia, PA: Society for Industrial and Applied Mathematics
Erscheinungsjahr
1993
Link zum Volltext
Quelle
Alma/SFX Local Collection
Beschreibungen/Notizen
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}$.