Parallel complexity of the subgraph connectivity problem

Lefteris Kirousis; Maria Serna; Paul Spirakis

doi:10.1109/sfcs.1989.63493

Parallel complexity of the subgraph connectivity problem

Lefteris Kirousis, Maria Serna, Paul Spirakis

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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.

Original language	English (US)
Title of host publication	Annual Symposium on Foundations of Computer Science (Proceedings)
Publisher	Publ by IEEE
Pages	294-299
Number of pages	6
ISBN (Print)	0818619821, 9780818619823
DOIs	https://doi.org/10.1109/sfcs.1989.63493
State	Published - 1989
Event	30th Annual Symposium on Foundations of Computer Science - Research Triangle Park, NC, USA Duration: Oct 30 1989 → Nov 1 1989

Publication series

Name	Annual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)	0272-5428

Other

Other	30th Annual Symposium on Foundations of Computer Science
City	Research Triangle Park, NC, USA
Period	10/30/89 → 11/1/89

ASJC Scopus subject areas

Hardware and Architecture

Access to Document

10.1109/sfcs.1989.63493

Cite this

Kirousis, L, Serna, M & Spirakis, P 1989, Parallel complexity of the subgraph connectivity problem. in Annual Symposium on Foundations of Computer Science (Proceedings). Annual Symposium on Foundations of Computer Science (Proceedings), Publ by IEEE, pp. 294-299, 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, NC, USA, 10/30/89. https://doi.org/10.1109/sfcs.1989.63493

@inproceedings{8ab16462284f42e6b3f8b63cc8e5170f,

title = "Parallel complexity of the subgraph connectivity problem",

abstract = "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.",

author = "Lefteris Kirousis and Maria Serna and Paul Spirakis",

year = "1989",

doi = "10.1109/sfcs.1989.63493",

language = "English (US)",

isbn = "0818619821",

series = "Annual Symposium on Foundations of Computer Science (Proceedings)",

publisher = "Publ by IEEE",

pages = "294--299",

booktitle = "Annual Symposium on Foundations of Computer Science (Proceedings)",

note = "30th Annual Symposium on Foundations of Computer Science ; Conference date: 30-10-1989 Through 01-11-1989",

}

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 -

Parallel complexity of the subgraph connectivity problem

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this