The computational complexity of disconnected cut and 2K2-partition

Conference paper


Martin, B. and Paulusma, D. 2011. The computational complexity of disconnected cut and 2K2-partition. The 17th International Conference on Principles and Practice of Constraint Programming (CP 2011). Perugia, Italy 12 - 16 Sep 2011 Springer. pp. 561-575 https://doi.org/10.1007/978-3-642-23786-7_43
TypeConference paper
TitleThe computational complexity of disconnected cut and 2K2-partition
AuthorsMartin, B. and 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.

Research GroupFoundations of Computing group
ConferenceThe 17th International Conference on Principles and Practice of Constraint Programming (CP 2011)
Page range561-575
ISSN0302-9743
ISBN
Hardcover9783642237850
PublisherSpringer
Publication dates
Print2011
Publication process dates
Deposited14 Jan 2013
Output statusPublished
Additional information

Martin B., Paulusma D. (2011) The Computational Complexity of Disconnected Cut and 2K2-Partition. In: Lee J. (eds) Principles and Practice of Constraint Programming – CP 2011. CP 2011. Lecture Notes in Computer Science, vol 6876. Springer, Berlin, Heidelberg

Digital Object Identifier (DOI)https://doi.org/10.1007/978-3-642-23786-7_43
LanguageEnglish
Book titlePrinciples and Practice of Constraint Programming – CP 2011
Permalink -

https://repository.mdx.ac.uk/item/83x16

  • 19
    total views
  • 0
    total downloads
  • 0
    views this month
  • 0
    downloads this month

Export as