TY - GEN
T1 - Hardness of bipartite expansion
AU - Khot, Subhash
AU - Saket, Rishi
PY - 2016/8/1
Y1 - 2016/8/1
N2 - 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 β, the goal is to find a subset V′ ⊆ V containing β 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 τ, γ > 0 there is no algorithm which, given a constant β > 0 and a bipartite graph G(U, V, E), runs in polynomial time and decides whether • (YES case) There is a subset S∗ ⊆ V s.t. S∗| ≥ β |V| satisfying | N(S∗)| ≤ γ |U|, or • (NO case) Any subset S ⊆ V s.t. |S| ≥ τβ|V| satisfies | N(S)| ≥ (1 - γ|U|, unless NP ⊆ ∩ϵoDTIME (2nϵ) 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 [23].
AB - 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 β, the goal is to find a subset V′ ⊆ V containing β 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 τ, γ > 0 there is no algorithm which, given a constant β > 0 and a bipartite graph G(U, V, E), runs in polynomial time and decides whether • (YES case) There is a subset S∗ ⊆ V s.t. S∗| ≥ β |V| satisfying | N(S∗)| ≤ γ |U|, or • (NO case) Any subset S ⊆ V s.t. |S| ≥ τβ|V| satisfies | N(S)| ≥ (1 - γ|U|, unless NP ⊆ ∩ϵoDTIME (2nϵ) 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 [23].
KW - Bipartite expansion
KW - Inapproximability
KW - PCP
KW - Submodular minimization
UR - http://www.scopus.com/inward/record.url?scp=85012960878&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85012960878&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ESA.2016.55
DO - 10.4230/LIPIcs.ESA.2016.55
M3 - Conference contribution
AN - SCOPUS:85012960878
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 24th Annual European Symposium on Algorithms, ESA 2016
A2 - Zaroliagis, Christos
A2 - Sankowski, Piotr
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 24th Annual European Symposium on Algorithms, ESA 2016
Y2 - 22 August 2016 through 24 August 2016
ER -