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 $\alpha >1$, and the goal is to design an $\alpha$-approximation algorithm with the fastest possible running time. We show the following results:

• An $r$-approximation for maximum independent set in $O^*(\exp(\tilde O(n/r \log^2 r+r\log^2r)))$ time,
• An $r$-approximation for chromatic number in $O^*(\exp(\tilde{O}(n/r \log r+r\log^2r)))$ time,
• A $(2-1\mathrm{/}r)$-approximation for minimum vertex cover in $O^{\ast }(\exp (n\mathrm{/}{r}^{\mathrm{\Omega }(r)}))$ time, and
• A $(k-1\mathrm{/}r)$-approximation for minimum $k$-hypergraph vertex cover in $O^{\ast }(\exp (n\mathrm{/}(kr{)}^{\mathrm{\Omega }(kr)}))$ time. (Throughout, $\tilde{O}$ and $O^{\ast }$ omit $\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}\mathrm{l}\mathrm{o}\mathrm{g}(r)$ and factors polynomial in the input size, respectively.) The best known time bounds for all problems were $O^{\ast }(2^{n\mathrm{/}r})$ [Bourgeois et al. 2009, 2011 & Cygan et al. 2008]. For maximum independent set and chromatic number, these bounds were complemented by $\exp (n^{1-o(1)}\mathrm{/}{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^{\ast }(2^{n\mathrm{/}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].