Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs

2011/07/11 by Marek Karpiński, Karpinski, Marek, Richard Schmied +3
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.1107.2000

openalex publication_date 2011/07/11 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

We establish almost tight upper and lower approximation bounds for the Vertex Cover problem on dense k-partite hypergraphs.

Related

• Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite\n Hypergraphs
• Approximating Vertex Cover in Dense Hypergraphs
• Tight Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs
• Vertex Cover Problem Parameterized Above and Below Tight Bounds
• Iterative Partial Rounding for Vertex Cover with Hard Capacities