On disconnected cuts and separators

For a connected graph G=(V,E)G=(V,E), a subset U⊆VU⊆V is called a disconnected cut if UU disconnects the graph, and the subgraph induced by UU is disconnected as well. A natural condition is to impose that for any u∈Uu∈U, the subgraph induced by (V∖U)∪{u}(V∖U)∪{u} is connected. In that case, UU 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, ss and tt, is NP-complete.