Parameterized Complexity of Satisfactory Partition Problem

Abstract

The Satisfactory Partition problem consists in deciding if the set of vertices of a given undirected graph can be partitioned into two nonempty parts such that each vertex has at least as many neighbours in its part as in the other part. The Balanced Satisfactory Partition problem is a variant of the above problem where the two partite sets are required to have the same cardinality. Both problems are known to be NP-complete. This problem was introduced by Gerber and Kobler [European J. Oper. Res. 125 (2000) 283-291] and further studied by other authors, but its parameterized complexity remains open until now. We enhance our understanding of the problem from the viewpoint of parameterized complexity. The three main results of the paper are the following: (1) The Satisfactory Partition problem is polynomial-time solvable for block graphs, (2) The Satisfactory Partition problem and its balanced version can be solved in polynomial time for graphs of bounded clicque-width, and (3) A generalized version of the Satisfactory Partition problem is W[1]-hard when parametrized by treewidth.