Vertex cover on 4-regular hyper-graphs is hard to approximate within 2 - ε
From MaRDI portal
Publication:3579212
DOI10.1145/509907.509986zbMath1192.68323OpenAlexW2166366531MaRDI QIDQ3579212
Publication date: 5 August 2010
Published in: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/509907.509986
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
Three‐query PCPs with perfect completeness over non‐Boolean domains, Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors, Approximating vertex cover in dense hypergraphs, A Characterization of hard-to-cover CSPs, Vertex cover might be hard to approximate to within \(2 - \varepsilon \), Disjoint bases in a polymatroid, Rainbow Coloring Hardness via Low Sensitivity Polymorphisms, Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs, Rainbow Coloring Hardness via Low Sensitivity Polymorphisms, Hardness of Rainbow Coloring Hypergraphs
