Bi-Covering: Covering Edges with Two Small Subsets of Vertices
| Autor: | Rohit Khandekar, MohammadTaghi Hajiaghayi, Guy Kortsarz, Rajiv Gandhi, Amey Bhangale |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
Unique games conjecture General Mathematics 0102 computer and information sciences 02 engineering and technology Disjoint sets Long code 01 natural sciences Graph Combinatorics Constant factor 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Bipartite graph 020201 artificial intelligence & image processing Mathematics |
| Zdroj: | SIAM Journal on Discrete Mathematics. 31:2626-2646 |
| ISSN: | 1095-7146 0895-4801 |
| Popis: | 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 such that every edge $e$ belongs to either the graph induced by $A$ or the graph induced by $B$. The goal is to minimize $\max\{|A|,|B|\}$. 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,\emptyset$ 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-\epsilon$ ratio algorithm for the problem, for any constant $\epsilon>0$. Given a bipartite graph, Max-Bi-Clique is a problem of finding the largest $k\times k$ complete bipartite subgraph. For the Max-Bi-Clique problem, a constant factor hardness was known un... |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|