On 23.04.2009 at 12:20 in S6, there is the following noon lecture:
The Disconnected Cut problem
University of Durham
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.
Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010