Complexity and approximation of satisfactory partition problems
Bazgan, Cristina; Tuza, Zsolt; Vanderpooten, Daniel (2005), Complexity and approximation of satisfactory partition problems, in Wang, Lusheng, Computing and Combinatorics 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-19, 2005, Proceedings, Springer : Berlin Heidelberg, p. 829-838
TypeCommunication / Conférence
Book titleComputing and Combinatorics 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-19, 2005, Proceedings
Book authorWang, Lusheng
MetadataShow full item record
Abstract (EN)The Satisfactory Partition problem consists of deciding if a given graph has a partition of its vertex set into two nonempty parts such that each vertex has at least as many neighbors in its part as in the other part. This problem was introduced by Gerber and Kobler in 1998 and further studied by other authors but its complexity remained open until now. We prove in this paper that Satisfactory Partition, as well as a variant where the parts are required to be of the same cardinality, are NP-complete. We also study approximation results for the latter problem, showing that it has no polynomial-time approximation scheme, whereas a constant approximation can be obtained in polynomial time. Similar results hold for balanced partitions where each vertex is required to have at most as many neighbors in its part as in the other part.
Subjects / KeywordsSatisfactory Partition Problem
Showing items related by title and author.