Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis?

Abstract. Obtaining lower bounds for NP-hard problems has for a long time been an active area of research. Recent algebraic techniques introduced by Jon-sson et al. (SODA 2013) show that the time complexity of the parameterized SAT(·) problem correlates to the lattice of strong partial clones. With this or-dering they isolated a relation R such that SAT(R) can be solved at least as fast as any other NP-hard SAT(·) problem. In this paper we extend this method and show that such languages also exist for the max ones problem (MAX-ONES(Γ)) and the Boolean valued constraint satisfaction problem over finite-valued constraint lan-guages (VCSP(∆)). With the help of these languages we relate MAX-ONES and VCSP to the exponential time hypothesis in several different ways.