Inapproximability of Minimum Vertex Cover on $k$-Uniform $k$-Partite Hypergraphs

DOI10.1137/130919416zbMath1331.68089OpenAlexW2048411223MaRDI QIDQ3453563

Sushant Sachdeva, Rishi Saket, Venkatesan Guruswami

Publication date: 27 November 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/130919416

zbMATH Keywords

hypergraphvertex coverinapproximabilityPCP

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)

Related Items (3)

Approximating the discrete time-cost tradeoff problem with bounded depth ⋮ Approximating the discrete time-cost tradeoff problem with bounded depth ⋮ Partitioning a graph into small pieces with applications to path transversal

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