{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:36:32Z","timestamp":1787322992130,"version":"build-2736575974"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>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 studied by Lov\u00e1sz, who gave a $\\frac{k}{2}$-approximation based on the standard LP relaxation. Subsequent work by Aharoni, Holzman, and Krivelevich showed a tight integrality gap of $(\\frac{k}{2} - o(1))$ for the LP relaxation. We further investigate the inapproximability of minimum vertex cover on $k$-uniform $k$-partite hypergraphs and present the following results (here $\\varepsilon &gt; 0$ is an arbitrarily small constant): NP-hardness of obtaining an approximation factor of $(\\frac{k}{4} - \\varepsilon)$ for even $k$ and $(\\frac{k}{4} - \\frac{1}{4k} - \\varepsilon)$ for odd $k$, NP-hardness of obtaining a nearly optimal approximation factor of $(\\frac{k}{2}-1+\\frac{1}{2k}-\\varepsilon)$, and an optimal unique games-hardness for approximation within factor $(\\frac{k}{2} - \\varepsilon)$, showing the optimality of Lov\u00e1sz's algorithm if one assumes the Unique Games conjecture. The first hardness result is based on a reduction from minimum vertex cover in $r$-uniform hypergraphs, for which NP-hardness of approximating within $r - 1 -\\varepsilon$ was shown by Dinur, Guruswami, Khot, and Regev. We include it for its simplicity, despite it being subsumed by the second hardness result. The unique games-hardness result is obtained by applying the results of Kumar, Manokaran, Tulsiani, and Vishnoi, with a slight modification, to the LP integrality gap due to Aharoni, Holzman, and Krivelevich. The modification ensures that the reduction preserves the desired structural properties of the hypergraph. The reduction for the nearly optimal NP-hardness result relies on the multilayered PCP of Dinur, Guruswami, Khot, and Regev and uses a gadget based on biased long codes adapted from the LP integrality gap of Aharoni, Holzman, and Krivelevich. Our reduction requires the analysis of several long codes with different biases, for which we prove structural properties of the so-called cross-intersecting collections of set families, variants of which have been studied in extremal set theory.<\/jats:p>","DOI":"10.1137\/130919416","type":"journal-article","created":{"date-parts":[[2015,1,6]],"date-time":"2015-01-06T12:26:18Z","timestamp":1420547178000},"page":"36-58","source":"Crossref","is-referenced-by-count":8,"title":["Inapproximability of Minimum Vertex Cover on $k$-Uniform $k$-Partite Hypergraphs"],"prefix":"10.1137","volume":"29","author":[{"given":"Venkatesan","family":"Guruswami","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sushant","family":"Sachdeva","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rishi","family":"Saket","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,1,6]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01844843"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-009-2332-6"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2011.v007a003"},{"key":"atypb6","first-page":"250","author":"Bansal N.","year":"2010","journal-title":"Proceedings of ICALP"},{"key":"atypb7","unstructured":"I. Dinur, V. Guruswami, and S. Khot,\n                      Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate Within Factor $(k$-3-$\\epsilon)$\n                      , ECCC technical report TR02-027, 2002."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704443057"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.439"},{"key":"atypb10","unstructured":"T. Feder, R. Motwani, L. O'Callaghan, R. Panigrahy, and D. Thomas,\n                      Online Distributed Predicate Evaluation\n                      , Technical report, Stanford University, Stanford, CA, 2003."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667055"},{"key":"atypb12","unstructured":"R. L. Graham, M. Gro\u0308tschel, and L. Lova\u0301sz, eds.\n                      Handbook of Combinatorics\n                      , Vol. 2, MIT Press, Cambridge, MA, 1995."},{"key":"atypb13","first-page":"360","author":"Guruswami V.","year":"2010","journal-title":"Proceedings of ICALP"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700381097"},{"key":"atypb16","first-page":"1005","author":"Holmerin J.","year":"2002","journal-title":"Proceedings of ICALP"},{"key":"atypb17","first-page":"310","author":"Ilie L.","year":"2005","journal-title":"Proceediings of CPM"},{"key":"atypb18","first-page":"1043","author":"Karakostas G.","year":"2005","journal-title":"Proceedings of ICALP"},{"key":"atypb19","first-page":"85","author":"Karp R. M.","year":"1972","journal-title":"New York"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"S. Khot,\n                      On the power of unique 2-prover 1-round games\n                      , in Proceedings of the 34th ACM STOC, 2002, pp. 767-775.","DOI":"10.1145\/509907.510017"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.019"},{"key":"atypb22","first-page":"1560","author":"Kumar A.","year":"2001","journal-title":"Proceedings of SODA"},{"key":"atypb23","first-page":"209","volume":"26","author":"Lova\u0301sz L.","year":"1975","journal-title":"Mathematiki Lapok"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"E. Mossel,\n                      Gaussian bounds for noise correlation of functions and tight analysis of long codes\n                      , in Proceedings of the 49th IEEE FOCS, 2008, pp. 156-165.","DOI":"10.1109\/FOCS.2008.44"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"P. Raghavendra,\n                      Optimal algorithms and inapproximability results for every CSP?\n                      , in Proceedings of the 40th ACM STOC, 2008, pp. 245-254.","DOI":"10.1145\/1374376.1374414"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"atypb27","first-page":"327","author":"Sachdeva S.","year":"2011","journal-title":"Proceedings of the APPROX-RANDOM"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"L. Trevisan,\n                      Non-approximability results for optimization problems on bounded degree instances\n                      , in Proceedings of the 33rd ACM STOC, 2001, pp. 453-461.","DOI":"10.1145\/380752.380839"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130919416","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:36:30Z","timestamp":1787319390000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130919416"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/130919416"],"URL":"https:\/\/doi.org\/10.1137\/130919416","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}