On the parameterized vertex cover problem for graphs with perfect matching  

作　　者：WANG JianXin LI WenJun LI ShaoHua CHEN JianEr 

机构地区：[1]School of Information Science and Engineering,Central South University [2]Department of Computer Science and Engineering,Texas A&M University,College Station

出　　处：《Science China(Information Sciences)》2014年第7期101-112,共12页中国科学（信息科学）（英文版）

基　　金：supported by National Natural Science Foundation of China(Grant Nos.61232001,61173051,61128006,71221061);Hunan Provincial Innovation Foundation For Postgraduate(Grant No.CX2011B088)

摘　　要：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 Konig 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.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 Konig 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.

关 键 词：NP-COMPLETE parameterized algorithm vertex cover iterative compression 

分 类 号：O157.5[理学—数学] O177.91[理学—基础数学]