ETH hardness for densest-k-subgraph with perfect completeness

DOI10.1137/1.9781611974782.86MaRDI QIDQ4575829zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

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
• Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• scientific article; zbMATH DE number 7758340 (Why is no real title available?)
• A note on hardness of computing recursive teaching dimension
• Detecting communities is hard (and counting them is even harder)
• Sum-of-squares lower bounds for densest \(k\)-subgraph
• 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)