A note on the satisfactory partition problem: Constant size requirement

A satisfactory partition is a partition of the vertex set V of a graph into two subsets such that each vertex has at least as many neighbors in the subset it belongs to as in the other subset. The definition can be generalized requiring that each vertex v has at least s(v) neighbors in the subset it belongs to, for a given function s : V → N. While the complexity of the problem of deciding if a graph admits a generalized satisfactory partition has been completely analized when s(v) is a function of the node degree, the issue had left open in the case s(v) is a constant. We prove that, for any constant k ≥ 2, the problem is NP-complete when s(v) = k for any v ∈ V .