On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs

DOI10.1007/978-3-642-14165-2_31zbMath1288.68093OpenAlexW1655051759MaRDI QIDQ3587391

Rishi Saket, Venkatesan Guruswami

Publication date: 7 September 2010

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-14165-2_31

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Hypergraph representation via axis-aligned point-subspace cover ⋮ Approximating vertex cover in dense hypergraphs ⋮ Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs ⋮ Approximation algorithms for orthogonal line centers ⋮ Recoverable Values for Independent Sets ⋮ Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs

This page was built for publication: On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs