We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

On disconnected cuts and separators.

Ito, T. and Kaminski, M. and Paulusma, Daniel and Thilikos, D.M. (2011) 'On disconnected cuts and separators.', Discrete applied mathematics., 159 (13). pp. 1345-1351.


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.

Item Type:Article
Keywords:Cut set, 2K2-partition, Retraction, Compaction.
Full text:Full text not available from this repository.
Publisher Web site:
Date accepted:No date available
Date deposited:No date available
Date of first online publication:August 2011
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar