## Abstract

In this paper, we develop new tools and connections for exponential time approximation. In this setting, we are given a problem instance and an integer r> 1 , and the goal is to design an approximation algorithm with the fastest possible running time. We give randomized algorithms that establish an approximation ratio of1.r for maximum independent set in O^{∗}(exp (O~ (n/ rlog ^{2}r+ rlog ^{2}r))) time,2.r for chromatic number in O^{∗}(exp (O~ (n/ rlog r+ rlog ^{2}r))) time,3.(2 - 1 / r) for minimum vertex cover in O^{∗}(exp (n/ r^{Ω}
^{(}
^{r}
^{)})) time, and4.(k- 1 / r) for minimum k-hypergraph vertex cover in O^{∗}(exp (n/ (kr) ^{Ω}
^{(}
^{k}
^{r}
^{)})) 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^{∗}(2 ^{n}
^{/}
^{r}) (Bourgeois et al. in Discret Appl Math 159(17):1954–1970, 2011; Cygan et al. in Exponential-time approximation of hard problems, 2008). For maximum independent set and chromatic number, these bounds were complemented by exp (n^{1}
^{-}
^{o}
^{(}
^{1}
^{)}/ r^{1}
^{+}
^{o}
^{(}
^{1}
^{)}) lower bounds (under the Exponential Time Hypothesis (ETH)) (Chalermsook et al. in Foundations of computer science, FOCS, pp. 370–379, 2013; Laekhanukit in Inapproximability of combinatorial problems in subexponential-time. Ph.D. thesis, 2014). Our results show that the naturally-looking O^{∗}(2 ^{n}
^{/}
^{r}) bounds are not tight for all these problems. The key to these results is a sparsification procedure that reduces a problem to a bounded-degree variant, allowing the use of approximation algorithms for bounded-degree graphs. To obtain 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 in J. ACM 63(3):27:1–27:32, 2016). It also implies that a (significant) improvement over our result will refute the gap-ETH conjecture (Dinur in Electron Colloq Comput Complex (ECCC) 23:128, 2016; Manurangsi and Raghavendra in A birthday repetition theorem and complexity of approximating dense CSPs, 2016).

Original language | English |
---|---|

Pages (from-to) | 3993-4009 |

Number of pages | 17 |

Journal | Algorithmica |

Volume | 81 |

Issue number | 10 |

DOIs | |

Publication status | Published - 1 Oct 2019 |

### Bibliographical note

Part of the following topical collections:•Special Issue: Parameterized and Exact Computation## Keywords

- Approximation algorithms
- Exponential time algorithms
- PCP’s
- PCP's