3
$\begingroup$

I have a tri-partite graph with three sets of vertices source, bridge and destination nodes. I want to find the shortest path between every vertex in the source set to every vertex in the destination vertex. Also, all vertices in the source set are connected to all vertices in the bridge set, and all the vertices in destination set are connected to all the vertices in the bridge set.

Let $n$ be the cardinality of both the source and the destination set, and $m$ be the cardinality of the bridge set.

A naive algorithm can compute these in $\mathcal{O}(n^{2}m)$ comparisons. On the other hand, since we are computing $n^{2}$ quantities, so the complexity will be at least $\mathcal{O}(n^{2})$.

My guess is that it can be done in $\mathcal{O}(n^{2}\log m)$ using priority-queue. So question is, whether my guess is correct and if not, then what is the complexity of solving this problem?

Tripartite Graph

Edit:

Note that shortest path between a vertex in the source set to any vertex in the bridge set is the direct link, and same holds for the shortest path between the bridge and destination set.

Improve this question
$\endgroup$
4
  • $\begingroup$ Good question. In my case, fortunately, the smallest $s_{i}\rightarrow b_{j}$ is the direct edge between $s_{i}$ and $b_{j}$. So it is allowed, but the link $s1 \rightarrow b2$ is guaranteed to smaller than any other path. $\endgroup$
    – arbitUser1401
    Feb 23, 2019 at 2:43
  • $\begingroup$ The same holds for edges from Bridge to destination $\endgroup$
    – arbitUser1401
    Feb 23, 2019 at 3:50
  • $\begingroup$ This is known as $(\min,+)$ matrix multiplication. $\endgroup$
    – Yuval Filmus
    Feb 23, 2019 at 4:34
  • $\begingroup$ So Naive algorithm is optimal (not considering faster matMults e.g. Strassen and other improvements)? $\endgroup$
    – arbitUser1401
    Feb 23, 2019 at 17:03

1 Answer 1

Reset to default
2
$\begingroup$

Your problem is essentially $(\min,+)$ matrix multiplication, also known as tropical matrix multiplication. This is because you're computing $$ C_{ik} = \min_j (A_{ij} + B_{jk}), $$ which is the same formula as usual matrix multiplication, with $\min$ replacing sum and $+$ replacing product.

Usual fast matrix multiplication algorithms cannot be used for this task. Furthermore, the APSP hypothesis in fine-grained complexity states that there is no $O(n^{3-\epsilon})$ algorithm for APSP. Since APSP reduces to logarithmically many tropical matrix multiplications, this implies that the latter also has no $O(n^{3-\epsilon})$ algorithms.

On the other hand, some $n^{o(1)}$ factors can be shaved, so for example a paper of Ryan Williams, Faster all-pairs shortest paths via circuit complexity.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.