On approximating minimum vertex cover for graphs with perfect matching (Q557830): Difference between revisions

Given a graph \(G\) the minimum vertex cover problem asks to find a minimum cardinality subset of vertices covering all edges of \(G\). The authors show that the problem is not easier for general graphs with perfect matching. For sparse graphs with perfect matching of average degree 5 they have given a 1.414-approximation algorithm. They note that an improvement of their results was given by \textit{M. Chlebík} and \textit{J. Chlebíková} [Lecture Notes in Computer Science 3153, 263--273 (2004; Zbl 1096.68061)].