Bi-covering: Covering edges with two small subsets of vertices

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 such that every edge e belongs to either the graph induced by A or the graph induced by B. The goal is to minimize maxfjAj; jBjg. This is the most simple case of the Channel Allocation problem [R. Gandhi et al., Networks, 47 (2006), pp. 225{236]. A solution that outputs V; ; gives ratio at most 2. We show that under a similar strong Unique Games Conjecture by Bansal and Khot [Optimal long code test with one free bit, in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS'09, IEEE, 2009, pp. 453{462] there is no 2-ϵ ratio algorithm for the problem, for any constant ϵ ≥ 0. Given a bipartite graph, Max-Bi-Clique is a problem of finding the largest k × k complete bipartite subgraph. For the Max-Bi-Clique problem, a constant factor hardness was known under a random 3-SAT hypothesis of Feige [Relations between average case complexity and approximation complexity, in Proceedings of the 34th Annual ACM Symposium on Theory of Computing, ACM, 2002, pp. 534{543] and also under the assumption that NP ⊈ ∩ ϵ > 0 DTIME(2nϵ ) [S. Khot, SIAM J. Comput., 36 (2006), pp. 1025{1071]. It was an open problem in [C. Ambühl, M. Mastrolilli, and O. Svensson, SIAM J. Comput., 40 (2011), pp. 567{596] to prove inapproximability of Max-Bi- Clique assuming weaker conjecture. Our result implies a 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, an exact algorithm for interval graphs, 1 + o(1) for minor free graphs, 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 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.