On the parameterized vertex cover problem for graphs with perfect matching Academic Article uri icon

abstract

  • A vertex cover of an n-vertex graph with perfect matching contains at least n/2 vertices. In this paper, we study the parameterized complexity of the problem vc-pm* that decides if a given graph with perfect matching has a vertex cover of size bounded by n/2 +k. We first present an algorithm of running time O*(4k) for a variation of the vertex cover problem on Knig graphs with perfect matching. This algorithm combined with the iterative compression technique leads to an algorithm of running time O*(9k) for the problem vc-pm*. Our result improves the previous best algorithm of running time O*(15k) for the vc-pm* problem, which reduces the problem to the almost 2-sat problem and solves the latter by Razgon and O'Sullivan's recent algorithm. 2014 Science China Press and Springer-Verlag Berlin Heidelberg.

published proceedings

  • Science China Information Sciences

author list (cited authors)

  • Wang, J., Li, W., Li, S., & Chen, J.

citation count

  • 4

complete list of authors

  • Wang, JianXin||Li, WenJun||Li, ShaoHua||Chen, JianEr

publication date

  • July 2014