Name
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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.jcss.2007.12.001 | J. Comput. Syst. Sci. |
Keywords | Field | DocType |
polynomial time approximation scheme,satisfiability,graph,polynomial time,np complete,approximation algorithm,complexity | Approximation algorithm,Discrete mathematics,Combinatorics,Vertex (geometry),Hardness of approximation,Vertex (graph theory),Neighbourhood (graph theory),Vertex cover,Polynomial-time approximation scheme,Mathematics,Feedback vertex set | Journal |
Volume | Issue | ISSN |
74 | 5 | 0022-0000 |
Citations | PageRank | References |
3 | 0.42 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Cristina Bazgan | 1 | 679 | 62.76 |
| Zsolt Tuza | 2 | 1889 | 262.52 |
| Daniel Vanderpooten | 3 | 1153 | 74.66 |