Are there conditional lower bounds for the deterministic time complexity of directed reachability algorithms? Maybe something linked to the Strong Exponential Time Hypothesis (SETH)?

I mean some result like, if SETH is true then reachability cannot be solved in less than $\mathcal{O}(something)$.

  • 2
    $\begingroup$ What exactly do you mean by "directed reachability algorithms"? If you mean: "given a graph on $n$ vertices, compute its transitive closure", then that is equivalent to Boolean Matrix Multiplication, so it takes $\Theta(n^\omega)$ time, where $\omega$ is the matrix multiplication exponent. $\endgroup$
    – Tassle
    Oct 26, 2023 at 16:07
  • $\begingroup$ Yes, I mean exactly that. Ok so as you said we can link it to the matrix multiplication lower bound. Is this in any way related to SAT and SETH? $\endgroup$ Oct 26, 2023 at 17:40
  • 2
    $\begingroup$ I don't know of any direct relation between Matrix Multiplication and SETH. There is another relevant conjecture here: that any "combinatorial" algorithm for boolean matrix multiplication requires essentially cubic time (up to subpolynomial factors). This would imply that any combinatorial algorithm for reachability requires essentially cubic time. Note however that "combinatorial" in this context isn't well defined, so it's a kind of informal conjecture. $\endgroup$
    – Tassle
    Oct 26, 2023 at 18:01
  • 2
    $\begingroup$ We don't know any non-trivial lower bounds on Matrix Multiplication under SETH, and there are some barriers to proving such lower bounds (see Theorem 4.4 in arxiv.org/pdf/2309.16176.pdf) $\endgroup$ Oct 31, 2023 at 18:12


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.