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 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 of \n \n 1. \n \n r for maximum independent set in O\xe2\x88\x97(exp(O~(n/rlog2r+rlog2r))) \n \ntime, \n \n2. \n \nr for chromatic number in O\xe2\x88\x97(exp(O~(n/rlogr+rlog2r))) \n \ntime, \n \n3. \n \n(2\xe2\x88\x921/r) \nfor minimum vertex cover in O\xe2\x88\x97(exp(n/r\xce\xa9(r))) \n \ntime, and \n \n4. \n \n(k\xe2\x88\x921/r) \nfor minimum k-hypergraph vertex cover in O\xe2\x88\x97(exp(n/(kr)\xce\xa9(kr))) \n \n time. \n \n \n(Throughout, O~ \nand O\xe2\x88\x97 omit polyloglog(r) and factors polynomial in the input size, respectively.) The best known time bounds for all problems were O\xe2\x88\x97(2n/r) (Bourgeois et al. in Discret Appl Math 159(17):1954\xe2\x80\x931970, 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(n1\xe2\x88\x92o(1)/r1+o(1)) lower bounds (under the Exponential Time Hypothesis (ETH)) (Chalermsook et al. in Foundations of computer science, FOCS, pp. 370\xe2\x80\x93379, 2013; Laekhanukit in Inapproximability of combinatorial problems in subexponential-time. Ph.D. thesis, 2014). Our results show that the naturally-looking O\xe2\x88\x97(2n/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\xe2\x80\x99s PCP (Chan in J. ACM 63(3):27:1\xe2\x80\x9327: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)