ETH hardness for densest-k-subgraph with perfect completeness

DOI10.1137/1.9781611974782.86zbMATH Open1409.68125arXiv1504.08352OpenAlexW772053521MaRDI QIDQ4575829FDOQ4575829

Authors: Mark Braverman, Young Kun-Ko, Aviad Rubinstein, O. 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)

Abstract: We show that, assuming the (deterministic) Exponential Time Hypothesis, distinguishing between a graph with an induced $k$-clique and a graph in which all k-subgraphs have density at most $1-epsilon$, requires $n^{ildeOmega(logn)}$ time. Our result essentially matches the quasi-polynomial algorithms of Feige and Seltser [FS97] and Barman [Bar15] for this problem, and is the first one to rule out an additive PTAS for Densest $k$-Subgraph. We further strengthen this result by showing that our lower bound continues to hold when, in the soundness case, even subgraphs smaller by a near-polynomial factor ($k^{\prime }=k{2}^{-ildeOmega(logn)}$) are assumed to be at most ($1-epsilon$)-dense. Our reduction is inspired by recent applications of the "birthday repetition" technique [AIM14,BKW15]. Our analysis relies on information theoretical machinery and is similar in spirit to analyzing a parallel repetition of two-prover games in which the provers may choose to answer some challenges multiple times, while completely ignoring other challenges.

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

Recommendations

• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Complexity of finding dense subgraphs
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Finding dense subgraphs of sparse graphs
• Finding dense subgraphs

Mathematics Subject Classification ID

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

Cited In (10)

• Sherali-Adams integrality gaps matching the log-density threshold
• From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
• Title not available (Why is that?)
• A note on hardness of computing recursive teaching dimension
• Sum-of-squares lower bounds for densest \(k\)-subgraph
• Detecting communities is hard (and counting them is even harder)
• Approximating Nash equilibria and dense subgraphs via an approximate version of Carathéodory's theorem
• Orienteering for electioneering

This page was built for publication: ETH hardness for densest-\(k\)-subgraph with perfect completeness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575829)