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

CC BY-SA 4.0
2019-11-06T23:05:14.893Z
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 (https://people.csail.mit.edu/virgi/6.s078/papers/nseth.pdf).
Huck Bennett
CC BY-SA 4.0
2019-11-07T01:10:24.557Z
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.
Alex Golovnev
<graph-algorithms><shortest-path><fine-grained>
Is APSP verification easier than APSP?
GMB
# Is APSP verification easier than APSP?

(Asked by: username_0 on 2019-11-06)

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?

**Tags:** graph-algorithms, shortest-path, fine-grained

> **Comments:**
> **username_1**: 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 (https://people.csail.mit.edu/virgi/6.s078/papers/nseth.pdf).  
> **username_2**: 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.  

---

## 0 answers

