Approximation of satisfactory bisection problems
Bazgan, Cristina; Tuza, Zsolt; Vanderpooten, Daniel (2008), Approximation of satisfactory bisection problems, Journal of Computer and System Sciences, 74, 5, p. 875-883. http://dx.doi.org/10.1016/j.jcss.2007.12.001
TypeArticle accepté pour publication ou publié
Journal nameJournal of Computer and System Sciences
MetadataShow full item record
Abstract (EN)The Satisfactory Bisection problem means to decide whether a given graph has a partition of its vertex set into two parts of the same cardinality such that each vertex has at least as many neighbors in its part as in the other part. A related variant of this problem, called Co-Satisfactory Bisection, requires that each vertex has at most as many neighbors in its part as in the other part. A vertex satisfying the degree constraint above in a partition is called ‘satisfied’ or ‘co-satisfied,’ respectively. After stating the NP-completeness of both problems, we study approximation results in two directions. We prove that maximizing the number of (co-)satisfied vertices in a bisection has no polynomial-time approximation scheme (unless P=NP), whereas constant approximation algorithms can be obtained in polynomial time. Moreover, minimizing the difference of the cardinalities of vertex classes in a bipartition that (co-)satisfies all vertices has no polynomial-time approximation scheme either.
Subjects / KeywordsApproximation algorithm; NP-complete; Complexity; Degree constraints; Vertex partition; Graph
Showing items related by title and author.