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

Amey Bhangale, Rajiv Gandhi, Mohammad T. Hajiaghayi, Rohit Khandekar, Guy Kortsarz

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

תקציר

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.

שפה מקוריתאנגלית
עמודים (מ-עד)2626-2646
מספר עמודים21
כתב עתSIAM Journal on Discrete Mathematics
כרך31
מספר גיליון4
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2017
פורסם באופן חיצוניכן

הערה ביבליוגרפית

Publisher Copyright:
© 2017 Society for Industrial and Applied Mathematics.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Bi-covering: Covering edges with two small subsets of vertices'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי