Abstract
We study the following basic problem called BiCovering. Given a graph G(V, E), find two (not necessarily disjoint) sets A subseteq V and B subseteq V such that A union B = V and that every edge e belongs to either the graph induced by A or to the graph induced by B. The goal is to minimize max{A, B}. This is the most simple case of the Channel Allocation problem [Gandhi et al., Networks, 2006]. A solution that outputs V,emptyset gives ratio at most 2. We show that under the similar Strong Unique Game Conjecture by [BansalKhot, FOCS, 2009] there is no 2  epsilon ratio algorithm for the problem, for any constant epsilon > 0.
Given a bipartite graph, Maxbiclique is a problem of finding largest k*k complete bipartite sub graph. For Maxbiclique problem, a constant factor hardness was known under random 3SAT hypothesis of Feige [Feige, STOC, 2002] and also under the assumption that NP !subseteq intersection_{epsilon > 0} BPTIME(2^{n^{epsilon}}) [Khot, SIAM J. on Comp., 2011]. It was an open problem in [Ambühl et. al., SIAM J. on Comp., 2011] to prove inapproximability of Maxbiclique assuming weaker conjecture. Our result implies similar hardness result assuming the Strong Unique Games Conjecture.
On the algorithmic side, we also give better than 2 approximation for BiCovering on numerous special graph classes. In particular, we get 1.876 approximation for Chordal graphs, exact algorithm for Interval Graphs, 1 + o(1) for Minor Free Graph, 2  4*delta/3 for graphs with minimum degree delta*n, 2/(1+delta^2/8) for deltavertex expander, 8/5 for Split Graphs, 2  (6/5)*1/d for graphs with minimum constant degree d etc. Our algorithmic results are quite nontrivial. In achieving these results, we use various known structural results about the graphs, combined with the techniques that we develop tailored to getting better than 2 approximation.
BibTeX  Entry
@InProceedings{bhangale_et_al:LIPIcs:2016:6272,
author = {Amey Bhangale and Rajiv Gandhi and Mohammad Taghi Hajiaghayi and Rohit Khandekar and Guy Kortsarz},
title = {{Bicovering: Covering Edges With Two Small Subsets of Vertices}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {6:16:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770132},
ISSN = {18688969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6272},
URN = {urn:nbn:de:0030drops62728},
doi = {10.4230/LIPIcs.ICALP.2016.6},
annote = {Keywords: Bicovering, Unique Games, Max Biclique}
}
Keywords: 

Bicovering, Unique Games, Max Biclique 
Collection: 

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) 
Issue Date: 

2016 
Date of publication: 

23.08.2016 