2011/12/31 by Marek Cygan, Holger Dell, Daniel Lokshtanov +8 · 4 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Conjecture #Constant (computer programming) #Deterministic algorithm #Discrete mathematics #Exponential function #Exponential time hypothesis #Integer (computer science) #Mathematics #Optimization and Search Problems #Time complexity #cs.CC #cs.DM #cs.DS
paper · pdf · doi:10.1145/2925416
published as ACM Trans. Algorithms 12(3): 41:1-41:24 (2016) · 25 pages, 1 figure
arxiv created 2014/03/27 · openalex publication_date 2016/05/24 · arxiv updated 2018/04/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
The field of exact exponential time algorithms for non-deterministic polynomial-time hard problems has thrived since the mid-2000s. While exhaustive search remains asymptotically the fastest known algorithm for some basic problems, non-trivial exponential time algorithms have been found for a myriad of problems, including G raph C oloring , H amiltonian P ath , D ominating S et , and 3-CNF-S at . In some instances, improving these algorithms further seems to be out of reach. The CNF-S at problem is the canonical example of a problem for which the trivial exhaustive search algorithm runs in time O (2 n ), where n is the number of variables in the input formula. While there exist non-trivial algorithms for CNF-S at that run in time o (2 n ), no algorithm was able to improve the growth rate 2 to a smaller constant, and hence it is natural to conjecture that 2 is the optimal growth rate. The strong exponential time hypothesis (SETH) by Impagliazzo and Paturi [JCSS 2001] goes a little bit further and asserts that, for every ϵ < 1, there is a (large) integer k such that k -CNF-S at cannot be computed in time 2 ϵ n . In this article, we show that, for every ϵ < 1, the problems H itting S et , S et S plitting , and NAE-S at cannot be computed in time O (2 ϵ n ) unless SETH fails. Here n is the number of elements or variables in the input. For these problems, we actually get an equivalence to SETH in a certain sense. We conjecture that SETH implies a similar statement for S et C over and prove that, under this assumption, the fastest known algorithms for S teiner T ree , C onnected V ertex C over , S et P artitioning , and the pseudo-polynomial time algorithm for S ubset S um cannot be significantly improved. Finally, we justify our assumption about the hardness of S et C over by showing that the parity of the number of solutions to S et C over cannot be computed in time O (2 ϵ n ) for any ϵ < 1 unless SETH fails.