Department of
Applied
Mathematics

The Disconnected Cut problem

Daniel Paulusma

University of Durham

Abstract

Let G=(V,E) be a finite connected undirected graph without multiple edges or self-loops. Let G[U] denote the subgraph induced by a subset U of V. Then U is a cut if G[V\U] is disconnected. We call a cut U a disconnected cut if G[U] is disconnected as well. This leads to the following decision problem

DISCONNECTED CUT Instance: A graph G Question: Does G have a disconnected cut?

As far as we know the computational complexity of this problem is open. We pinpoint relationships with other graph-theoretic concepts such as graph homomorphisms and graph contractions, discuss partial results and mention other related open (sub)problems.