论文标题
部分顶点覆盖有界变性的图表
Partial Vertex Cover on Graphs of Bounded Degeneracy
论文作者
论文摘要
在部分顶点封面（PVC）问题中，我们得到了$ n $ vertex Graph $ g $和一个正整数$ k $，其目标是找到一个$ k $的顶点子集$ s $ s $ k $最大化边缘的数量，至少$ s $中的一个端点。这个问题是一般图上的w [1] - hard，但在平面和apex-minor freegraphs上，在运行时间$ 2^{o（\ sqrt {k}）} n^{o（1）} $的参数化子指定时间算法$ 2^{o（\ sqrt {k}）} n^{o（1）} $。 （FSTTCS 2009，IPL 2011）]和a $ k^{o（k）} n^{o（1）} $ time算法在有限的退化图上[Amini等。 （FSTTCS 2009，JCSS 2011）]。有界退化的图形包含许多稀疏的图形类，例如平面图，$ h $ -minor的免费图和有限的树宽度图。在这项工作中，我们证明了以下结果： 1）在有界退化的图上，PVC有一种pvc算法$ 2^{o（k）} n^{o（1）} $，这是对先前的$ k^{o（k）} n^{o（k）} n^{o（o（k）} n^{o（1）$ time algorithm by Amini et al e e e e e e e eT eT e e eT eT的改进。 2）PVC在有界退化的图上接受多项式压缩，解决了Amini等人提出的开放问题。
In the Partial Vertex Cover (PVC) problem, we are given an $n$-vertex graph $G$ and a positive integer $k$, and the objective is to find a vertex subset $S$ of size $k$ maximizing the number of edges with at least one end-point in $S$. This problem is W[1]-hard on general graphs, but admits a parameterized subexponential time algorithm with running time $2^{O(\sqrt{k})}n^{O(1)}$ on planar and apex-minor free graphs [Fomin et al. (FSTTCS 2009, IPL 2011)], and a $k^{O(k)}n^{O(1)}$ time algorithm on bounded degeneracy graphs [Amini et al. (FSTTCS 2009, JCSS 2011)]. Graphs of bounded degeneracy contain many sparse graph classes like planar graphs, $H$-minor free graphs, and bounded tree-width graphs. In this work, we prove the following results: 1) There is an algorithm for PVC with running time $2^{O(k)}n^{O(1)}$ on graphs of bounded degeneracy which is an improvement on the previous $k^{O(k)}n^{O(1)}$ time algorithm by Amini et al. 2) PVC admits a polynomial compression on graphs of bounded degeneracy, resolving an open problem posed by Amini et al.
