Approximation of satisfactory bisection problems |
| |
Authors: | Cristina Bazgan Zsolt Tuza Daniel Vanderpooten |
| |
Affiliation: | aUniversité Paris-Dauphine, LAMSADE, Place du Marechal de Lattre de Tassigny, 75775 Paris Cedex 16, France;bComputer and Automation Institute, Hungarian Academy of Sciences, H-1111 Budapest, Kende u. 13-17, Hungary;cDepartment of Computer Science, University of Pannonia, Veszprém, Hungary |
| |
Abstract: | 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. |
| |
Keywords: | Graph Vertex partition Degree constraints Complexity NP-complete Approximation algorithm |
本文献已被 ScienceDirect 等数据库收录! |
|