ETH Hardness for Densest-k-Subgraph with Perfect Completeness

DOI10.1137/1.9781611974782.86zbMath1409.68125arXiv1504.08352OpenAlexW772053521MaRDI QIDQ4575829

Aviad Rubinstein, Young Kun-Ko, Mark Braverman, Omri Weinstein

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1504.08352

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Density (toughness, etc.) (05C42)

Related Items (8)

Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis ⋮ Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem ⋮ Orienteering for electioneering ⋮ A note on hardness of computing recursive teaching dimension ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: ETH Hardness for Densest-k-Subgraph with Perfect Completeness