On disconnected cuts and separators

Takehiro Ito; Marcin Kamiski; Danil Paulusma; Dimitrios M. Thilikos

doi:10.1016/j.dam.2011.04.027

On disconnected cuts and separators

Takehiro Ito, Marcin Kamiski, Danil Paulusma, Dimitrios M. Thilikos

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

For a connected graph G=(V,E), a subset U⊆V is called a disconnected cut if U disconnects the graph, and the subgraph induced by U is disconnected as well. A natural condition is to impose that for any u∈U, the subgraph induced by (V\U)∪u is connected. In that case, U is called a minimal disconnected cut. We show that the problem of testing whether a graph has a minimal disconnected cut is NP-complete. We also show that the problem of testing whether a graph has a disconnected cut separating two specified vertices, s and t, is NP-complete.

Original language	English (US)
Pages (from-to)	1345-1351
Number of pages	7
Journal	Discrete Applied Mathematics
Volume	159
Issue number	13
DOIs	https://doi.org/10.1016/j.dam.2011.04.027
State	Published - Aug 6 2011

Keywords

2-partition
Compaction
Cut set
Retraction

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2011.04.027

Cite this

@article{89480f7ab76f46aba397d81e603f8219,

title = "On disconnected cuts and separators",

abstract = "For a connected graph G=(V,E), a subset U⊆V is called a disconnected cut if U disconnects the graph, and the subgraph induced by U is disconnected as well. A natural condition is to impose that for any u∈U, the subgraph induced by (V\U)∪u is connected. In that case, U is called a minimal disconnected cut. We show that the problem of testing whether a graph has a minimal disconnected cut is NP-complete. We also show that the problem of testing whether a graph has a disconnected cut separating two specified vertices, s and t, is NP-complete.",

keywords = "2-partition, Compaction, Cut set, Retraction",

author = "Takehiro Ito and Marcin Kamiski and Danil Paulusma and Thilikos, {Dimitrios M.}",

year = "2011",

month = aug,

day = "6",

doi = "10.1016/j.dam.2011.04.027",

language = "English (US)",

volume = "159",

pages = "1345--1351",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "13",

}

TY - JOUR

T1 - On disconnected cuts and separators

AU - Ito, Takehiro

AU - Kamiski, Marcin

AU - Paulusma, Danil

AU - Thilikos, Dimitrios M.

PY - 2011/8/6

Y1 - 2011/8/6

N2 - For a connected graph G=(V,E), a subset U⊆V is called a disconnected cut if U disconnects the graph, and the subgraph induced by U is disconnected as well. A natural condition is to impose that for any u∈U, the subgraph induced by (V\U)∪u is connected. In that case, U is called a minimal disconnected cut. We show that the problem of testing whether a graph has a minimal disconnected cut is NP-complete. We also show that the problem of testing whether a graph has a disconnected cut separating two specified vertices, s and t, is NP-complete.

AB - For a connected graph G=(V,E), a subset U⊆V is called a disconnected cut if U disconnects the graph, and the subgraph induced by U is disconnected as well. A natural condition is to impose that for any u∈U, the subgraph induced by (V\U)∪u is connected. In that case, U is called a minimal disconnected cut. We show that the problem of testing whether a graph has a minimal disconnected cut is NP-complete. We also show that the problem of testing whether a graph has a disconnected cut separating two specified vertices, s and t, is NP-complete.

KW - 2-partition

KW - Compaction

KW - Cut set

KW - Retraction

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

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

U2 - 10.1016/j.dam.2011.04.027

DO - 10.1016/j.dam.2011.04.027

M3 - Article

AN - SCOPUS:79959552582

SN - 0166-218X

VL - 159

SP - 1345

EP - 1351

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 13

ER -

On disconnected cuts and separators

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this