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

DOI10.1137/130919416MaRDI QIDQ3453563zbMATH OpenOpenAlexFDO

Authors 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

hypergraphinapproximabilityvertex coverPCP

Mathematics Subject Classification ID

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

Recommendations

• On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs
• Nearly optimal NP-hardness of vertex cover on \(k\)-uniform \(k\)-partite hypergraphs
• scientific article; zbMATH DE number 2086690
• Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs
• Inapproximability of hypergraph vertex cover and applications to scheduling problems
• An approximation algorithm for the partial vertex cover problem in hypergraphs
• On approximation of the vertex cover problem in hypergraphs
• Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs
• A randomised approximation algorithm for the partial vertex cover problem in hypergraphs
• Inapproximability of \(b\)-matching in \(k\)-uniform hypergraphs

Cited in

(10)

• Nearly optimal NP-hardness of vertex cover on \(k\)-uniform \(k\)-partite hypergraphs
• Partitioning a graph into small pieces with applications to path transversal
• On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs
• Approximating the discrete time-cost tradeoff problem with bounded depth
• Approximating the discrete time-cost tradeoff problem with bounded depth
• scientific article; zbMATH DE number 2086690 (Why is no real title available?)
• Inapproximability of hypergraph vertex cover and applications to scheduling problems
• A new multilayered {PCP} and the hardness of hypergraph vertex cover
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs

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

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