A faster algorithm for Vertex Cover parameterized by solution size
David G. Harris, N. S. Narayanaswamy
我们用运行时 O^*(1.25284^k) 来描述顶点覆盖的新算法,其中 k 是所需解决方案的大小,并且 O^* 在输入大小中隐藏多项式因子。 这比以前的运行时间有所改善,因为陈,Kanj,Xia(2010)已经超过10年。 O^*(1.2738^k) 我们的算法的关键是使用一个潜在的函数,该函数同时跟踪k以及顶点覆盖LP松弛的最佳值λ。 这种方法还允许我们在边界度图和高于保证的Vertex Cover中使用先前算法进行最大独立设置。 算法的主要步骤是在高度顶点上分支,同时确保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 f...