Computing Densest $k$-Subgraph with Structural Parameters

\textsc{Densest $k$-Subgraph} is the problem to find a vertex subset $S$ of size $k$ such that the number of edges in the subgraph induced by $S$ is maximized. In this paper, we show that \textsc{Densest $k$-Subgraph} is fixed parameter tractable when parameterized by neighborhood diversity, block deletion number, distance-hereditary deletion number, and cograph deletion number, respectively. Furthermore, we give a $2$-approximation $2^{\text{tc}(G)\mathrm{/}2}{n}^{O(1)}$-time algorithm where $\text{tc}(G)$ is the twin cover number of an input graph $G$.