Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs

DOI10.1007/978-3-642-22935-0_28zbMath1343.68100arXiv1105.4175OpenAlexW2131906507MaRDI QIDQ3088105

Rishi Saket, Sushant Sachdeva

Publication date: 17 August 2011

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1105.4175

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

Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs

Cites Work

• On the hardness of approximating minimum vertex cover
• Uniformly cross intersecting families
• On a theorem of Lovász on covers in \(r\)-partite hypergraphs
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• Proof verification and the hardness of approximation problems
• Schema mapping discovery from data instances
• On the power of unique 2-prover 1-round games
• Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems
• On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs
• Probabilistic checking of proofs
• A Parallel Repetition Theorem
• Non-approximability results for optimization problems on bounded degree instances
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• Some optimal inapproximability results
• Combinatorial Pattern Matching
• Automata, Languages and Programming
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item