We study the following basic problem called Bi-Covering. Given a graph G ( V E ) , find two (not necessarily disjoint) sets A V and B V such that A 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 gives ratio at most 2 . We show that under the similar {\em Strong} Unique Game Conjecture by [Bansal-Khot, FOCS, 2009] there is no 2 − ratio algorithm for the problem, for any constant 0"> 0 .

Given a bipartite graph, Max-bi-clique is a problem of finding largest k k complete bipartite sub graph. For Max-bi-clique problem, a constant factor hardness was known under random 3-SAT hypothesis of Feige [Feige, STOC, 2002] and also under the assumption that 0} BPTIME(2^{n^\epsilon})"> N P 0 B PTIM E ( 2 n ) [Khot, SIAM J. on Comp., 2011]. It was an open problem in [Amb{\"u}hl et. al., SIAM J. on Comp., 2011] to prove inapproximability of Max-bi-clique 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 Bi-Covering 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 3 for graphs with minimum degree n , 2 (1 + 2 8) for -vertex expander, 8 5 for Split Graphs, 2 − ( 6 5) 1 d for graphs with minimum constant degree d etc. Our algorithmic results are quite non-trivial. 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.