Parameterized algorithms for the Happy Set problem

In this paper we study the parameterized complexity for the problem (): For an undirected graph and a subset of vertices, a vertex is if and all its neighbors are in ; otherwise . Given an undirected graph and an integer , the goal of is to find a subset of vertices such that the number of happy vertices is maximized. In this paper we first show that is W[1]-hard with respect to even if the input graph is a split graph. Then, we prove the fixed-parameter tractability of when parameterized by tree-width, by clique-width plus , by neighborhood diversity, or by cluster deletion number.