Algorithmic approach to the satisfactory graph partitioning problem

In a given graph, we want to partition the set of its vertices in two subsets, such that each vertex is satisfied in that it has at least as many neighbours in its own subset as in the other. By introducing weights for the vertices and the edges, we generalize the problem. These more general problems are strongly NP-complete. For the unweighted version, we present some sufficient conditions for the existence of a solution, and propose an exact and a heuristic solution method.