Skip to main content

Research Repository

Advanced Search

The computational complexity of Disconnected Cut and 2K2-Partition

Martin, B.; Paulusma, D.

Authors

B. Martin



Contributors

Jimmy Lee
Editor

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

Citation

Martin, B., & Paulusma, D. (2011). The computational complexity of Disconnected Cut and 2K2-Partition. In J. Lee (Ed.), Principles and practice of constraint programming, 17th International Conference, CP 2011, 12-16 September 2011, Perugia, Italy ; proceedings (561-575). https://doi.org/10.1007/978-3-642-23786-7_43

Conference Name Principles and Practice of Constraint Programming, 17th International Conference, CP 2011
Conference Location Perugia, Italy
Publication Date Jan 1, 2011
Deposit Date Dec 6, 2011
Pages 561-575
Series Title Lecture notes in computer science
Series Number 6876
Series ISSN 0302-9743,1611-3349
Book Title Principles and practice of constraint programming, 17th International Conference, CP 2011, 12-16 September 2011, Perugia, Italy ; proceedings.
ISBN 9783642237850
DOI https://doi.org/10.1007/978-3-642-23786-7_43
Public URL https://durham-repository.worktribe.com/output/1158287


You might also like



Downloadable Citations