CMSC 858F: Algorithmic Lower Bounds Fall 2014 Parameterized reductions and assumptions
Mohammad Taghi Hajiaghayi, Sina Dehghani · 2014
Definition 1 ETH: there is no 2 time algorithm for n variable 3-SAT. (the current best bound is 1.30704 [1]). Note that an n-variable 3-SAT can have Ω(n) clauses but Impagliazzo et al. [2] show that there is a 2-time algorithm for n-variable 3-SAT iff there is a 2-time algorithm for m-clause 3-SAT. Thus ETH also says: There is no 2-time algorithm for m-clause 3-SAT. The standard textbook NP-hardness reduction from 3-SAT to 3-coloring constructs a graph of O(n+m) = O(m) edges and O(n+m) = O(m) vertices to solve 3-SAT instance of n-variables and m-clauses. Thus assuming ETH, there is no 2 algorithm for 3-coloring on an n-vertex graph G. Since there are many standard polynomial-time reductions from 3-coloring to many other problems such that the reduction increases the number of vertices by at most a constant factor, we have