论文标题
与结构参数的计算密集$ k $ -subgraph
Computing Densest $k$-Subgraph with Structural Parameters
论文作者
论文摘要
\ textsc {conenest $ k $ -subgraph}是找到一个尺寸$ k $的顶点子集$ s $的问题，因此最大化了由$ s $引起的子图中的边缘数。在本文中，我们表明\ textsc {cuentest $ k $ -subgraph}分别通过邻里多样性，块删除号，距离遗传删除数字和cograph删除编号进行参数时是固定的参数。此外，我们给出了$ 2 $ -Approximation $ 2^{\ tc（g）/2} n^{o（1）} $ - 时间算法，其中$ \ tc（g）$是输入图$ g $的双封面$。
\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$.
