New tools and connections for exponential-time approximation

In this paper, we develop new tools and connections for exponential time approximation. In this setting, we are given a problem instance and a parameter α>1, and the goal is to design an α-approximation algorithm with the fastest possible running time. We show the following results: - An r-approximation for maximum independent set in O∗(exp(O~(n/rlog2r+rlog2r))) time, - An r-approximation for chromatic number in O∗(exp(O~(n/rlogr+rlog2r))) time, - A (2−1/r)-approximation for minimum vertex cover in O∗(exp(n/rΩ(r))) time, and - A (k−1/r)-approximation for minimum k-hypergraph vertex cover in O∗(exp(n/(kr)Ω(kr))) time. (Throughout, O~ and O∗ omit polyloglog(r) and factors polynomial in the input size, respectively.) The best known time bounds for all problems were O∗(2n/r) [Bourgeois et al. 2009, 2011 & Cygan et al. 2008]. For maximum independent set and chromatic number, these bounds were complemented by exp(n1−o(1)/r1+o(1)) lower bounds (under the Exponential Time Hypothesis (ETH)) [Chalermsook et al., 2013 & Laekhanukit, 2014 (Ph.D. Thesis)]. Our results show that the naturally-looking O∗(2n/r) bounds are not tight for all these problems. The key to these algorithmic results is a sparsification procedure, allowing the use of better approximation algorithms for bounded degree graphs. For obtaining the first two results, we introduce a new randomized branching rule. Finally, we show a connection between PCP parameters and exponential-time approximation algorithms. This connection together with our independent set algorithm refute the possibility to overly reduce the size of Chan's PCP [Chan, 2016]. It also implies that a (significant) improvement over our result will refute the gap-ETH conjecture [Dinur 2016 & Manurangsi and Raghavendra, 2016].