In APSP, the input is an $n$-node directed weighted graph $G$, and the output is an $n \times n$ matrix holding pairwise shortest path distances between nodes in $G$. Define "APSP-Verification" as the problem where we get a graph $G$ and a matrix $D$, and the goal is to decide whether or not $D$ is the correct output of APSP on $G$. Is there an algorithm that solves this problem in $O(n^{3-c})$ time, for any absolute constant $c>0$? Alternately, taking the standard conjecture in fine-grained complexity that no algorithm solves APSP in $O(n^{3-c})$ time, can we prove that there is no such algorithm for APSP-Verification?

  • 4
    $\begingroup$ It's a great and natural question. I don't think that this is known (I would be very interested if it is), but, as I'm sure you know, the answer to the analogous question is "yes" for 3-SUM (people.csail.mit.edu/virgi/6.s078/papers/nseth.pdf). $\endgroup$ Nov 6, 2019 at 23:05
  • 3
    $\begingroup$ While I don't know how to solve APSP-verification in sub-cubic time, note that APSP can be verified in truly sub-cubic time with some additional short witness: Corollary 3 in the paper pointed out by Huck. $\endgroup$ Nov 7, 2019 at 1:10


Your Answer

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