The Computational Complexity of Disconnected Cut and 2K2-Partition

Barnaby Martin, Daniel Paulusma

For a connected graph G=(V,E), a subset U of V is called a disconnected cut if U disconnects the graph and the subgraph induced by U is disconnected as well. We show that the probl…