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?
2
-
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$– Huck BennettCommented 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$– Alex GolovnevCommented Nov 7, 2019 at 1:10
Add a comment
|