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

Given a bipartite graph, Max-bi-clique is a problem of finding largest $k\times 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 $NP\not\subseteq \mathop{\cap}_{\epsilon>0} BPTIME(2^{n^\epsilon})$ [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\delta/3$ for graphs with minimum degree $\delta n$, $2/(1+\delta^2/8)$ for $\delta$-vertex expander, $8/5$ for Split Graphs, $2-(6/5)\cdot 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.