Circuits and Backdoors: Five Shades of the SETH

The Strong Exponential Time Hypothesis (SETH) is a standard assumption in (fine-grained) parameterized complexity and many tight lower bounds are based on it. We consider a number of reasonable weakenings of the SETH, with sources from (i) circuit complexity (ii) backdoors for SAT-solving (iii) graph width parameters and (iv) weighted satisfiability problems. Our goal is to arrive at formulations which are simultaneously more plausible as hypotheses, but also capture interesting and robust notions of complexity. Using several tools from classical complexity theory we are able to consolidate these numerous hypotheses into a hierarchy of five main equivalence classes of increasing solidity. This framework serves as a step towards structurally classifying a variety of SETH-based lower bounds into intermediate equivalence classes.

To illustrate the applicability of our framework, for each of our classes we give at least one (non-SAT) problem which is equivalent to the class as a characteristic example application. As our main showcase, we consider a natural parameterization of Independent Set by vertex deletion distance from several standard graph classes. Our framework allows us to make connections that would have previously been hard to see: for instance, we consider the question of whether (Weighted) Independent Set can be solved faster than 2 k n O(1) on graphs which are k vertices away from a class C where the problem is tractable, such as interval graphs or cographs. We provide precise characterizations of the difficulty of breaking such bounds, in particular proving that obtaining (2 -ε) k n O(1) time algorithms for Cograph+kv or Block+kv graphs is equivalent to obtaining a fast satisfiability algorithm for circuits of depth εn; while solving the weighted version for Interval+kv graphs is equivalent to the (seemingly) harder problem of obtaining a fast satisfiability algorithm for SAT parameterized by a 2-SAT backdoor.