论文标题
通过解决方案尺寸参数的顶点覆盖的更快的算法
A faster algorithm for Vertex Cover parameterized by solution size
论文作者
论文摘要
我们描述了一种新算法，用于带有运行时$ o^*（1.25284^k）$的顶点盖，其中$ k $是所需解决方案的大小，$ o^*$ hide yides多项式因子在输入大小中。由于Chen，Kanj和＆Xia（2010年）的$ o^*（1.2738^k）$的$ o^*（1.2738^k）（2010年）持续了十多年。我们算法的关键是使用一个潜在功能，该功能同时跟踪$ k $以及顶点盖LP放松的最佳值$λ$。这种方法还允许我们利用先前的算法，以最大程度地独立设置在有限度图中和高于保证的顶点覆盖物中。 该算法的主要步骤是分支高度顶点，同时确保$ k $和$μ= k -λ$在每个步骤中都减少。图中可能会有局部障碍，以防止$μ$在此过程中减少；我们开发了许多新颖的分支步骤来处理这些情况。
We describe a new algorithm for vertex cover with runtime $O^*(1.25284^k)$, where $k$ is the size of the desired solution and $O^*$ hides polynomial factors in the input size. This improves over previous runtime of $O^*(1.2738^k)$ due to Chen, Kanj, & Xia (2010) standing for more than a decade. The key to our algorithm is to use a potential function which simultaneously tracks $k$ as well as the optimal value $λ$ of the vertex cover LP relaxation. This approach also allows us to make use of prior algorithms for Maximum Independent Set in bounded-degree graphs and Above-Guarantee Vertex Cover. The main step in the algorithm is to branch on high-degree vertices, while ensuring that both $k$ and $μ= k - λ$ are decreased at each step. There can be local obstructions in the graph that prevent $μ$ from decreasing in this process; we develop a number of novel branching steps to handle these situations.
