The computational complexity of disconnected cut and 2K2-partition

Martin, B.; Paulusma, D.

Abstract

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 2K2-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.

Citation

Martin, B., & Paulusma, D. (2015). The computational complexity of disconnected cut and 2K2-partition. Journal of Combinatorial Theory, Series B, 111, 17-37. https://doi.org/10.1016/j.jctb.2014.09.002

• Journal Article Type: Article
• Online Publication Date: Sep 26, 2014
• Publication Date: Mar 1, 2015
• Deposit Date: Dec 20, 2014
• Publicly Available Date: Mar 26, 2016
• Journal: Journal of Combinatorial Theory, Series B
• Print ISSN: 0095-8956
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 111
• Pages: 17-37
• DOI: https://doi.org/10.1016/j.jctb.2014.09.002
• Keywords: Graph theory, Disconnected cut, 2K2-partition, Biclique cover.
• Public URL: https://durham-repository.worktribe.com/output/1415061