[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

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

  • Conference paper
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX 2011, RANDOM 2011)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 6845))

  • 1578 Accesses

Abstract

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 general k, the problem was studied by Lovász [23], who gave a \(\frac{k}{2}\)-approximation based on the standard LP relaxation. Subsequent work by Aharoni, Holzman and Krivelevich [1] showed a tight integrality gap of \(\left(\frac{k}{2} - o(1)\right)\) for the LP relaxation. While this problem was known to be NP-hard for k ≥ 3, the first non-trivial NP-hardness of approximation factor of \(\frac{k}{4}-\varepsilon \) was shown in a recent work by Guruswami and Saket [13]. They also showed that assuming Khot’s Unique Games Conjecture yields a \(\frac{k}{2}-\varepsilon \) inapproximability for this problem, implying the optimality of Lovász’s result.

In this work, we show that this problem is NP-hard to approximate within \(\frac{k}{2}-1+\frac{1}{2k}-\varepsilon \). This hardness factor is off from the optimal by an additive constant of at most 1 for k ≥ 4. Our reduction relies on the Multi-Layered PCP of [8] and uses a gadget – based on biased Long Codes – adapted from the LP integrality gap of [1]. The nature of 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.

Research supported in part by NSF grants CCF-0832797, 0830673, and 0528414.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 35.99
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 44.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Aharoni, R., Holzman, R., Krivelevich, M.: On a theorem of Lovász on covers in r-partite hypergraphs. Combinatorica 16(2), 149–174 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  2. Alon, N., Lubetzky, E.: Uniformly cross intersecting families. Combinatorica 29(4), 389–431 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  3. Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. J. ACM 45(3), 501–555 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  4. Arora, S., Safra, S.: Probabilistic checking of proofs: A new characterization of NP. J. ACM 45(1), 70–122 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  5. Austrin, P., Khot, S., Safra, M.: Inapproximability of vertex cover and independent set in bounded degree graphs. Theory of Computing 7(1), 27–43 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  6. Bansal, N., Khot, S.: Inapproximability of hypergraph vertex cover and applications to scheduling problems. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 250–261. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  7. Dinur, I., Guruswami, V., Khot, S.: Vertex cover on k-uniform hypergraphs is hard to approximate within factor (k-3-ε). ECCC Technical Report TR02-027 (2002)

    Google Scholar 

  8. Dinur, I., Guruswami, V., Khot, S., Regev, O.: A new multilayered pcp and the hardness of hypergraph vertex cover. SIAM J. Comput. 34, 1129–1146 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  9. Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Annals of Mathematics 162, 439–485 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  10. Feder, T., Motwani, R., O’Callaghan, L., Panigrahy, R., Thomas, D.: Online distributed predicate evaluation. Technical Report, Stanford University (2003)

    Google Scholar 

  11. Gottlob, G., Senellart, P.: Schema mapping discovery from data instances. J. ACM 57(2) (January 2010)

    Google Scholar 

  12. Graham, R.L., Grötschel, M., Lovász, L. (eds.): Handbook of combinatorics, vol. 2. MIT Press, Cambridge (1995)

    MATH  Google Scholar 

  13. Guruswami, V., Saket, R.: On the inapproximability of vertex cover on k-partite k-uniform hypergraphs. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 360–371. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  14. Håstad, J.: Some optimal inapproximability results. J. ACM 48(4), 798–859 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  15. Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM J. Comput. 31(5), 1608–1623 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  16. Holmerin, J.: Improved inapproximability results for vertex cover on k-uniform hypergraphs. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, p. 1005. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  17. Ilie, L., Solis-Oba, R., Yu, S.: Reducing the size of NFAs by using equivalences and preorders. In: Apostolico, A., Crochemore, M., Park, K. (eds.) CPM 2005. LNCS, vol. 3537, pp. 310–321. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  18. Karakostas, G.: A better approximation ratio for the vertex cover problem. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 1043–1050. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  19. Karp, R.M.: Reducibility among combinatorial problems. Complexity of Computer Computations, 85–103 (1972)

    Google Scholar 

  20. Khot, S.: On the power of unique 2-prover 1-round games. In: Proc. 34th ACM STOC, pp. 767–775 (2002)

    Google Scholar 

  21. Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci. 74(3), 335–349 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  22. Kumar, A., Manokaran, R., Tulsiani, M., Vishnoi, N.K.: On LP-based approximability for strict CSPs. In: Proc. SODA (2011)

    Google Scholar 

  23. Lovász, L.: On minimax theorems of combinatorics. Doctoral Thesis, Mathematiki Lapok 26, 209–264 (1975)

    Google Scholar 

  24. Mossel, E.: Gaussian bounds for noise correlation of functions and tight analysis of long codes. In: Proc. 49th IEEE FOCS, pp. 156–165 (2008)

    Google Scholar 

  25. Raghavendra, P.: Optimal algorithms and inapproximability results for every CSP? In: Proc. 40th ACM STOC, pp. 245–254 (2008)

    Google Scholar 

  26. Raz, R.: A parallel repetition theorem. SIAM J. Comput. 27(3), 763–803 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  27. Trevisan, L.: Non-approximability results for optimization problems on bounded degree instances. In: Proc. 33rd ACM STOC, pp. 453–461 (2001)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Princeton University, Princeton, NJ, 08540, USA

    Sushant Sachdeva & Rishi Saket

Authors
  1. Sushant Sachdeva
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Rishi Saket
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, University of Liverpool, Ashton Building, L69 3BX, Liverpool, UK

    Leslie Ann Goldberg

  2. Department of Computer Science, University of Kiel, Olshausenstr. 40, 24098, Kiel, Germany

    Klaus Jansen

  3. Tepper School of Business, Carnegie Mellon University, 5000 Forbes Avenue, 15213, Pittsburgh, PA, USA

    R. Ravi

  4. Centre Universitaire d’Informatique,, University of Geneva,, Battelle A 7 route de Drize, 1227, Carouge, Switzerland

    José D. P. Rolim

Rights and permissions

Reprints and permissions

Copyright information

© 2011 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Sachdeva, S., Saket, R. (2011). Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs. In: Goldberg, L.A., Jansen, K., Ravi, R., Rolim, J.D.P. (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2011 2011. Lecture Notes in Computer Science, vol 6845. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22935-0_28

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-22935-0_28

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-22934-3

  • Online ISBN: 978-3-642-22935-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation