Martin, B. and Paulusma, Daniel (2011) 'The computational complexity of disconnected cut and 2K2-partition.', in Principles and practice of constraint programming, 17th International Conference, CP 2011, 12-16 September 2011, Perugia, Italy ; proceedings. Berlin: Springer, pp. 561-575. Lecture notes in computer science. (6876).
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. We show that the problem to test whether a graph has a disconnected cut is NP-complete. This problem is polynomially equivalent to the following problems: testing if a graph has a 2K 2-partition, testing if a graph allows a vertex-surjective homomorphism to the reflexive 4-cycle and testing if a graph has a spanning subgraph that consists of at most two bicliques. Hence, as an immediate consequence, these three decision problems are NP-complete as well. This settles an open problem frequently posed in each of the four settings.
|Item Type:||Book chapter|
|Full text:||Full text not available from this repository.|
|Publisher Web site:||http://dx.doi.org/10.1007/978-3-642-23786-7_43|
|Record Created:||03 Jan 2012 15:35|
|Last Modified:||03 Apr 2013 16:24|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Usage statistics||Look up in GoogleScholar | Find in a UK Library|