Open Collections

From Gap-ETH to FPT Inapproximability: Clique, Dominating Set, and More

Banff International Research Station for Mathematical Innovation and Discovery

Finding k-clique in a graph can trivially be done in time n^{O(k)}, and this is more or less tight if one assumes the Exponential Time Hypothesis (ETH). Now, given the existence of a clique of much larger size, e.g. exp(exp(exp(k))), can we find a k-clique much faster Similar questions can be asked for maximum dominating set, maximum induced planar subgraph, and many other problems of this nature. In this work, we show that the answers for these questions are likely to be negative: An n^{o(k)} time algorithm for many of these problems will break the Gap-ETH assumption [Dinur'16, Manurangsi-Raghavendra'16], i.e., it will imply 0.99 approximation for 3SAT that runs in sub-exponential time. Breaking Gap-ETH seems beyond the reach of current algorithmic techniques. [joint work with M. Cygan, G. Kortsarz, B. Laekhanukit, P. Manurangsi, D. Nanongkai, L. Trevisan, to appear in FOCS 2017]

Mathematics; Computer science; Operations research, mathematical programming; Theoretical computer science

video/mp4

Author affiliation: Aalto University

2019-03-12

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/68610

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/