Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis

DOI10.4230/LIPIcs.ICALP.2017.79zbMath1441.68191OpenAlexW2741464441MaRDI QIDQ5111410

Pasin Manurangsi

Publication date: 27 May 2020

Full work available at URL: https://doi.org/10.4230%2FLIPIcs.ICALP.2017.79

zbMATH Keywords

hardness of approximationsmall set expansion hypothesis

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 (8)

Partitioning subclasses of chordal graphs with few deletions ⋮ Partitioning subclasses of chordal graphs with few deletions ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ LP Relaxation and Tree Packing for Minimum $k$-Cut ⋮ Fast and Deterministic Approximations for k-Cut. ⋮ Unnamed Item ⋮ 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: Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis