On disconnected cuts and separators

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

Research output: Contribution to journalArticlepeer-review


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 languageEnglish (US)
Pages (from-to)1345-1351
Number of pages7
JournalDiscrete Applied Mathematics
Issue number13
StatePublished - Aug 6 2011


  • 2-partition
  • Compaction
  • Cut set
  • Retraction

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'On disconnected cuts and separators'. Together they form a unique fingerprint.

Cite this