Bicovering: Covering edges with two small subsets of vertices

DOI10.4230/LIPIcs.ICALP.2016.6zbMath1388.68210OpenAlexW2529968156MaRDI QIDQ4598138

Rohit Khandekar, Rajiv Gandhi, Amey Bhangale, Guy Kortsarz, Mohammad Taghi Hajiaghayi

Publication date: 19 December 2017

Full work available at URL: https://doi.org/10.4230/lipics.icalp.2016.6

zbMATH Keywords

unique gamesbi-coveringmax bi-clique

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (3)

From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ On the complexity of fair house allocation ⋮ Tight inapproximability of minimum maximal matching on bipartite graphs and related problems

This page was built for publication: Bicovering: Covering edges with two small subsets of vertices