Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > MULTILAYERED LABEL COVER:
Reports tagged with Multilayered Label Cover:
TR13-071 | 8th May 2013
Venkatesan Guruswami, Sushant Sachdeva, Rishi Saket

Inapproximability of Minimum Vertex Cover on k-uniform k-partite Hypergraphs

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 can be computed in polynomial time. For k \ge 3, this problem is known to be NP-hard. For general k, the problem was ... more >>>




ISSN 1433-8092 | Imprint