Name
Abstract | ||
|---|---|---|
The SATISFACTORY PARTITION problem consists in 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 [Partitioning a graph to satisfy all vertices, Technical report, Swiss Federal Institute of Technology, Lausanne, 1998; Algorithmic approach to the satisfactory graph partitioning problem, European J. Oper. Res. 125 (2000) 283-291] 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. However, for graphs with maximum degree at most 4 the problem is polynomially solvable. We also study generalizations and variants of this problem where a partition into k nonempty parts (k ≥ 3) is requested. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.dam.2005.10.014 | Discrete Applied Mathematics |
Keywords | Field | DocType |
satisfactory partition,swiss federal institute,maximum degree,satisfactory partition problem,satisfactory graph,k nonempty part,polynomially solvable,european j. oper,complexity,polynomial algorithm,graph,np-complete.,nonempty part,algorithmic approach | Partition problem,Discrete mathematics,Combinatorics,Level structure,Rank of a partition,Frequency partition of a graph,Degree (graph theory),Graph partition,Feedback vertex set,Mathematics,Domatic number | Journal |
Volume | Issue | ISSN |
154 | 8 | Discrete Applied Mathematics |
Citations | PageRank | References |
11 | 0.72 | 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 |