Parameterized complexity of satisfactory partition problem

Abstract

Given an undirected graph G, we study the Satisfactory Partition problem, where the goal is to decide whether it is possible to partition the vertex set of G into two parts such that each vertex has at least as many neighbours in its own 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 (2000) [9] 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 main results of the paper are the following: (1) Satisfactory Partition is polynomial-time solvable for block graphs, (2) Satisfactory Partition and Balanced Satisfactory Partition are fixed parameter tractable (FPT) when parameterized by neighbourhood diversity. (3) Satisfactory Partition and its balanced version can be solved in polynomial time for graphs of bounded clique-width, and (4) Balanced Satisfactory Partition is W[1]-hard when parameterized by treewidth.