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|
|Date accepted:||No date available|
|Date deposited:||No date available|
|Date of first online publication:||2011|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|