New Tools and Connections for Exponential-time Approximation
share
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^*((Õ(n/r ^2 r+r^2r))) time, - An r-approximation for chromatic number in O^*((Õ(n/r r+r^2r))) time, - A (2-1/r)-approximation for minimum vertex cover in O^*((n/r^Ω(r))) time, and - A (k-1/r)-approximation for minimum k-hypergraph vertex cover in O^*((n/(kr)^Ω(kr))) time. (Throughout, Õ and O^* omit polyloglog(r) and factors polynomial in the input size, respectively.) The best known time bounds for all problems were O^*(2^n/r) [Bourgeois et al. 2009, 2011 & Cygan et al. 2008]. For maximum independent set and chromatic number, these bounds were complemented by (n^1-o(1)/r^1+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^*(2^n/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].
READ FULL TEXT