\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^{\tc(G)/2}n^{O(1)}$-time algorithm where $\tc(G)$ is the twin cover number of an input graph $G$.
翻译：\ textsc{ enest $k$- Subgraph} 是问题所在, 无法找到一个大小为 S $S 的顶端子子集 $S $k$, 从而最大限度地增加 $S 引出的子图边缘数 。 在本文中, 我们显示 \ textsc{ Denest $k$- Subgraph} 是一个固定的参数, 当分别按街区多样性、 区块删除号、 远程- 地球删除号 和 cophic 删除号 来参数 。 此外, 我们给出了 $2 $- approximation $2\ tc( G)/2}n\\\ O(1)} $- 时间算法, $\ tc( G) 是输入图$G 的双封面号 。
相关内容
微信扫码咨询专知VIP会员