On approximating minimum vertex cover for graphs with perfect matching

DOI10.1016/J.TCS.2004.12.034MaRDI QIDQ557830zbMATH OpenOpenAlexFDO

Authors Iyad Kanj, Jianer Chen

Publication date 30 June 2005

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2004.12.034

zbMATH Keywords

approximation algorithmgraph matchinginapproximabilityminimum vertex cover

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Review text

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)].

Recommendations

• scientific article; zbMATH DE number 2080241
• Computing and Combinatorics
• On the parameterized vertex cover problem for graphs with perfect matching
• An approximation of the minimum vertex cover in a graph
• scientific article; zbMATH DE number 5631194
• scientific article; zbMATH DE number 7399666
• On approximation of max-vertex-cover
• On the approximability of the vertex cover and related problems
• On perfect matchings in matching covered graphs
• On the hardness of approximating minimum vertex cover

Cites work

• Efficient bounds for the stable set, vertex cover and set packing problems
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• scientific article; zbMATH DE number 3889282 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1559516 (Why is no real title available?)
• scientific article; zbMATH DE number 910871 (Why is no real title available?)
• Improved non-approximability results for minimum vertex cover with density constraints
• Mathematical Foundations of Computer Science 2004
• On approximation properties of the independent set problem for low degree graphs
• Ramsey numbers and an approximation algorithm for the vertex cover problem
• The importance of being biased
• Vertex packings: Structural properties and algorithms

Cited in

(10)

• Equivalence between the minimum covering problem and the maximum matching problem
• A note on minimal matching covered graphs
• Maintaining a large matching and a small vertex cover
• Backdoors to satisfaction
• scientific article; zbMATH DE number 2080241 (Why is no real title available?)
• Computing and Combinatorics
• The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number
• The complexity of König subgraph problems and above-guarantee vertex cover
• On the counting version of the maximum 2-satisfiability problem
• On the parameterized vertex cover problem for graphs with perfect matching

This page was built for publication: On approximating minimum vertex cover for graphs with perfect matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q557830)