Manurangsi, Pasin
Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum kCut from the Small Set Expansion Hypothesis
Abstract
The Small Set Expansion Hypothesis (SSEH) is a conjecture which roughly states that it is NPhard to distinguish between a graph with a small set of vertices whose expansion is almost zero and one in which all small sets of vertices have expansion almost one. In this work, we prove conditional inapproximability results for the following graph problems based on this hypothesis:
 Maximum Edge Biclique (MEB): given a bipartite graph G, find a complete bipartite subgraph of G with maximum number of edges. We show that, assuming SSEH and that NP != BPP, no polynomial time algorithm gives n^{1  epsilon}approximation for MEB for every constant epsilon > 0.
 Maximum Balanced Biclique (MBB): given a bipartite graph G, find a balanced complete bipartite subgraph of G with maximum number of vertices. Similar to MEB, we prove n^{1  epsilon} ratio inapproximability for MBB for every epsilon > 0, assuming SSEH and that NP != BPP.
 Minimum kCut: given a weighted graph G, find a set of edges with minimum total weight whose removal splits the graph into k components. We prove that this problem is NPhard to approximate to within (2  epsilon) factor of the optimum for every epsilon > 0, assuming SSEH.
The ratios in our results are essentially tight since trivial algorithms give napproximation to both MEB and MBB and 2approximation algorithms are known for Minimum kCut [Saran and Vazirani, SIAM J. Comput., 1995].
Our first two results are proved by combining a technique developed by Raghavendra, Steurer and Tulsiani [Raghavendra et al., CCC, 2012] to avoid locality of gadget reductions with a generalization of Bansal and Khot's long code test [Bansal and Khot, FOCS, 2009] whereas our last result is shown via an elementary reduction.
BibTeX  Entry
@InProceedings{manurangsi:LIPIcs:2017:7500,
author = {Pasin Manurangsi},
title = {{Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum kCut from the Small Set Expansion Hypothesis}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {79:179:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7500},
URN = {urn:nbn:de:0030drops75004},
doi = {10.4230/LIPIcs.ICALP.2017.79},
annote = {Keywords: Hardness of Approximation, Small Set Expansion Hypothesis}
}
07.07.2017
Keywords: 

Hardness of Approximation, Small Set Expansion Hypothesis 
Seminar: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Issue date: 

2017 
Date of publication: 

07.07.2017 