The computational complexity of disconnected cut and 2K2-partition
(2014)
Journal Article
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
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 pr... Read More about The computational complexity of disconnected cut and 2K2-partition.