TY - GEN

T1 - Parallel complexity of the subgraph connectivity problem

AU - Kirousis, Lefteris

AU - Serna, Maria

AU - Spirakis, Paul

PY - 1989

Y1 - 1989

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0024771050&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024771050&partnerID=8YFLogxK

U2 - 10.1109/sfcs.1989.63493

DO - 10.1109/sfcs.1989.63493

M3 - Conference contribution

AN - SCOPUS:0024771050

SN - 0818619821

SN - 9780818619823

T3 - Annual Symposium on Foundations of Computer Science (Proceedings)

SP - 294

EP - 299

BT - Annual Symposium on Foundations of Computer Science (Proceedings)

PB - Publ by IEEE

T2 - 30th Annual Symposium on Foundations of Computer Science

Y2 - 30 October 1989 through 1 November 1989

ER -