Partial Vertex Cover on Graphs of Bounded Degeneracy
share
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(√(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.
READ FULL TEXT