Document Open Access Logo

Hardness of Bipartite Expansion

Authors Subhash Khot, Rishi Saket

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.55.pdf
  • Filesize: 0.5 MB
  • 17 pages

Document Identifiers

Author Details

Subhash Khot
Rishi Saket

Cite As Get BibTex

Subhash Khot and Rishi Saket. Hardness of Bipartite Expansion. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 55:1-55:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.55

Abstract

We study the natural problem of estimating the expansion of subsets of vertices on one side of a bipartite graph. More precisely, given a bipartite graph G(U,V,E) and a parameter beta, the goal is to find a subset V' subseteq V containing beta fraction of the vertices of V which minimizes the size of  N(V'), the neighborhood of V'. This problem, which we call Bipartite Expansion, is a special case of submodular minimization subject to a cardinality constraint, and is also related to other problems in graph partitioning and expansion. Previous to this work, there was no hardness of approximation known for Bipartite Expansion. 

In this paper we show the following strong inapproximability for Bipartite Expansion: for any constants tau, gamma > 0
there is no algorithm which, given a constant beta > 0 and a bipartite graph G(U,V,E), runs in polynomial time and decides whether 
 
- (YES case) There is a subset S^* subseteq V s.t. |S^*| >= beta*|V| satisfying |N(S^*)| <= gamma |U|, or 
 
- (NO case) Any subset S subseteq V s.t. |S| >= tau*beta*|V| satisfies |N(S)| >=  (1 - gamma)|U|, unless 
NP subseteq intersect_{epsilon > 0}{DTIME}(2^{n^epsi;on}) i.e. NP has subexponential time algorithms.

We note that our hardness result stated above is a vertex expansion analogue of the Small Set (Edge) Expansion Conjecture of
Raghavendra and Steurer 2010.

Subject Classification

Keywords
  • inapproximability
  • bipartite expansion
  • PCP
  • submodular minimization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. A. Agarwal, M. Charikar, K. Makarychev, and Y. Makarychev. O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems. In Proceedings of the ACM Symposium on the Theory of Computing, pages 573-581, 2005. Google Scholar
  2. N. Alon. Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory. Combinatorica, 6(3):207-219, 1986. Google Scholar
  3. C. Ambühl, M. Mastrolilli, and O. Svensson. Inapproximability results for maximum edge biclique, minimum linear arrangement, and sparsest cut. SIAM Journal of Computing, 40(2):567-596, 2011. Google Scholar
  4. B. Applebaum, B. Barak, and A. Wigderson. Public-key cryptography from different assumptions. In Proceedings of the ACM Symposium on the Theory of Computing, pages 171-180, 2010. Google Scholar
  5. S. Arora, S. Rao, and U. V. Vazirani. Expander flows, geometric embeddings and graph partitioning. Journal of the ACM, 56(2):1-37, 2009. Google Scholar
  6. P. Austrin and S. Khot. A simple deterministic reduction for the gap minimum distance of code problem. In Proceedings of ICALP, pages 474-485, 2011. Google Scholar
  7. S. Chawla, R. Krauthgamer, R. Kumar, Y. Rabani, and D. Sivakumar. On the hardness of approximating multicut and sparsest-cut. Computational Complexity, 15(2):94-114, 2006. Google Scholar
  8. Q. Cheng and D. Wan. A deterministic reduction for the gap minimum distance problem: [extended abstract]. In Proceedings of the ACM Symposium on the Theory of Computing, pages 33-38, 2009. Google Scholar
  9. I. Dumer, D. Micciancio, and M. Sudan. Hardness of approximating the minimum distance of a linear code. IEEE Trans. Information Theory, 49(1):22-37, 2003. Google Scholar
  10. U. Feige. Relations between average case complexity and approximation complexity. In Proceedings of the ACM Symposium on the Theory of Computing, pages 534-543, 2002. Google Scholar
  11. U. Feige, M. Hajiaghayi, and J. R. Lee. Improved approximation algorithms for minimum weight vertex separators. SIAM Journal of Computing, 38(2):629-657, 2008. Google Scholar
  12. V. Guruswami, C. Umans, and S. P. Vadhan. Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. Journal of the ACM, 56(4), 2009. Google Scholar
  13. S. Khot. On the power of unique 2-prover 1-round games. In Proceedings of the ACM Symposium on the Theory of Computing, pages 767-775, 2002. Google Scholar
  14. S. Khot. Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM Journal of Computing, 36(4):1025-1071, 2006. Google Scholar
  15. S. Khot and N. K. Vishnoi. The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into 𝓁₁. In Proceedings of the Annual Symposium on Foundations of Computer Science, pages 53-62, 2005. Google Scholar
  16. F. T. Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM, 46(6):787-832, 1999. Google Scholar
  17. N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215-245, 1995. Google Scholar
  18. R. J. Lipton and R. E. Tarjan. Applications of a planar separator theorem. SIAM Journal of Computing, 9(3):615-627, 1980. Google Scholar
  19. A. Louis, P. Raghavendra, and S. Vempala. The complexity of approximating vertex expansion. In Proceedings of the Annual Symposium on Foundations of Computer Science, pages 360-369, 2013. Google Scholar
  20. A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3):261-227, 1988. Google Scholar
  21. R. Müller and D. Wagner. α-vertex separator is NP-hard even for 3-regular graphs. Computing, 46:343-353, 1991. Google Scholar
  22. N. Pippenger. Sorting and selecting in rounds. SIAM Journal of Computing, 16(6):1032-1038, 1987. Google Scholar
  23. P. Raghavendra and D. Steurer. Graph expansion and the unique games conjecture. In Proceedings of the ACM Symposium on the Theory of Computing, pages 755-764, 2010. Google Scholar
  24. P. Raghavendra, D. Steurer, and M. Tulsiani. Reductions between expansion problems. In Proceedings of the Annual IEEE Conference on Computational Complexity, pages 64-73, 2012. Google Scholar
  25. A. Rao. Randomness Extractors for Independent Sources and Applications. PhD thesis, University of Texas at Austin, 2007. Google Scholar
  26. M. Sipser and D. A. Spielman. Expander codes. IEEE Transactions on Information Theory, 42(6):1710-1722, 1996. Google Scholar
  27. Z. Svitkina and L. Fleischer. Submodular approximation: Sampling-based algorithms and lower bounds. SIAM Journal of Computing, 40(6):1715-1737, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact