Improved Parameterized Complexity of Happy Set Problems

Abstract

We present fixed-parameter tractable (FPT) algorithms for two problems, Maximum Happy Set (MaxHS) and Maximum Edge Happy Set (MaxEHS)--also known as Densest k-Subgraph. Given a graph $G$ and an integer $k$, MaxHS asks for a set $S$ of $k$ vertices such that the number of $\text{happy vertices}$ with respect to $S$ is maximized, where a vertex $v$ is happy if $v$ and all its neighbors are in $S$. We show that MaxHS can be solved in time $\mathcal{O}\left(2^{\text{mw}}\cdot \text{mw}\cdot k^2\cdot |V(G)|\right)$ and $\mathcal{O}\left(8^{\text{cw}}\cdot k^2\cdot |V(G)|\right)$, where $\text{mw}$ and $\text{cw}$ denote the $\text{modular-width}$ and the $\text{clique-width}$ of $G$, respectively. This resolves the open questions posed in literature. The MaxEHS problem is an edge-variant of MaxHS, where we maximize the number of $\text{happy edges}$, the edges whose endpoints are in $S$. In this paper we show that MaxEHS can be solved in time $f(\text{nd})\cdot |V(G){|}^{\mathcal{O}(1)}$ and $\mathcal{O}\left(2^{\text{cd}}\cdot k^2\cdot |V(G)|\right)$, where $\text{nd}$ and $\text{cd}$ denote the $\text{neighborhood diversity}$ and the $\text{cluster deletion number}$ of $G$, respectively, and $f$ is some computable function. This result implies that MaxEHS is also fixed-parameter tractable by $\text{twin cover number}$.