Approximated Vertex Cover for Graphs with Perfect Matchings

Tomokazu IMAMURA  Kazuo IWAMA  Tatsuie TSUKIJI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E89-D   No.8   pp.2405-2410
Publication Date: 2006/08/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e89-d.8.2405
Print ISSN: 0916-8532
Type of Manuscript: INVITED PAPER (Special Section on Invited Papers from New Horizons in Computing)
Category: 
Keyword: 
approximation algorithm,  vertex cover,  perfect matching,  MAX-2SAT,  

Full Text: PDF(214.4KB)>>
Buy this Article




Summary: 
Chen and Kanj considered the VERTEX COVER problem for graphs with perfect matchings (VC-PM). They showed that: (i) There is a reduction from general VERTEX COVER to VC-PM, which guarantees that if one can achieve an approximation factor of less than two for VC-PM, then one can do so for general VERTEX COVER as well. (ii) There is an algorithm for VC-PM whose approximation factor is given as 1.069+0.069 where is the average degree of the given graph. In this paper we improve (ii). Namely we give a new VC-PM algorithm which greatly outperforms the above one and its approximation factor is roughly . Our algorithm also works for graphs with "large" matchings, although its approximation factor is degenerated.