License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2016.55
URN: urn:nbn:de:0030-drops-63971
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6397/
Go to the corresponding LIPIcs Volume Portal

Khot, Subhash ; Saket, Rishi

Hardness of Bipartite Expansion

pdf-format:
LIPIcs-ESA-2016-55.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{khot_et_al:LIPIcs:2016:6397,
  author =	{Subhash Khot and Rishi Saket},
  title =	{{Hardness of Bipartite Expansion}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{55:1--55:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Piotr Sankowski and Christos Zaroliagis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6397},
  URN =		{urn:nbn:de:0030-drops-63971},
  doi =		{10.4230/LIPIcs.ESA.2016.55},
  annote =	{Keywords: inapproximability, bipartite expansion, PCP, submodular minimization}
}

Keywords: inapproximability, bipartite expansion, PCP, submodular minimization
Collection: 24th Annual European Symposium on Algorithms (ESA 2016)
Issue Date: 2016
Date of publication: 18.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI