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

Sushant Sachdeva, Rishi Saket

We study the problem of computing the minimum vertex cover on k-uniform k-partite hypergraphs when the k-partition is given. On bipartite graphs (k = 2), the minimum vertex cover c…