The satisfactory partition problem

The satisfactory partition problem
∗ † ∗Cristina Bazgan Zsolt Tuza Daniel Vanderpooten
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 [GK98, GK00] and further studied by other authors but its complexity re-
mained 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 solv-
able. We also study generalizations and variants of this problem where a partition into k
nonempty parts (k ≥ 3) is requested.
Keywords: Satisfactorypartition,graph,complexity,polynomialalgorithm,NP-complete.
1 Introduction
GerberandKoblerintroducedin[GK98,GK00]theproblemofdecidingifagivengraphhasa
vertexpartitionintotwononemptypartssuchthateachvertexhasatleastasmanyneighbors
in its part as in the other part. A graph satisfying this property is called partitionable.
As remarked by Gerber and Kobler, Satisfactory Partition may have no solution. In
particular, the following graphs are not partitionable: complete graphs, stars, and complete
bipartite graphs with at least one of the two vertex sets having odd size. Some other graphs
areeasilypartitionable: cyclesoflengthatleast4, ...