3
$\begingroup$

I am searching for an algorithm to check whether a complete, undirected graph is fullfilling the triangle inequality( $\text{weight}(u,v) \le \text{weight}(u,w) + \text{weight}(w,v)$ for all vertices $u, v, w$).

My first naive try was to use an algorithm for solving the all-pairs-shortest-path-problem and compare the result to the vertices connecting two nodes directly.

However, I think this might be overkill. Is there any better way to check?

Thanks a lot.

$\endgroup$
  • $\begingroup$ Why do you need to compute APSP if the graph is complete? $\endgroup$ – adrianN Nov 8 '13 at 17:09
  • $\begingroup$ Hint: use matrix multiplication - with a bet of modifications, and your lower bound is the lower of the fastest matrix multiplication algorithm. $\endgroup$ – AJed Nov 8 '13 at 19:56
6
$\begingroup$

Yes. If you have a complete graph, the simplest algorithm is to enumerate all triangles and check whether each one satisfies the inequality. In practice, this will also likely be the best solution unless your graphs are very large and you need the absolute best possible performance. For instance, enumeration will likely be faster than most shortest-paths algorithms.

None of the shortest-path algorithms provide better asymptotic runtime; they are more complicated to implement; and they will be slower in practice (because of a larger constant factor).

As AJed correctly points out, you can use matrix multiplication to beat the $O(n^3)$ bound. However, this requires a bit more care. While there are algorithms for matrix multiplication that are faster than $O(n^3)$ time, the algorithms are tricky to implement, so if you take this approach, you might want to use an existing library/implementation (e.g., BLAS). Also, the asymptotically optimal algorithms (e.g., Coppersmith/Winograd, Stothers, Williams) only become faster once $n$ becomes extremely large so they won't be worthwhile in practice. This suggests that if you want to wring out every last bit of performance, you'll need to actually benchmark this on realistic workloads: asymptotic complexity can be misleading.

If you care about extreme optimization, cache effects may also play a huge role here, so the way the graph is laid out in memory may have a significant effect on the constant factors. Fortunately, if your graph is represented as an adjacency matrix, standard libraries for matrix multiplication already take this into account.

If it were me, I'd just enumerate all triangles and check the triangle inequality. If you run into a problem domain where this is the bottleneck in the overall computation and where it is too slow, then you could consider more sophisticated approaches, like using matrix multiplication, at that point. To paraphrase Knuth, "Premature optimization is the root of all evil".

$\endgroup$
  • 1
    $\begingroup$ I don't get it why you say that enumeration is the best. Can you prove it? $\endgroup$ – AJed Nov 9 '13 at 3:17
  • 1
    $\begingroup$ @AJed, I added a more careful statement. Thank you for prodding me on this point! $\endgroup$ – D.W. Nov 9 '13 at 3:22
  • $\begingroup$ Can we prove that reducing it to matrix multiplication is the best way? $\endgroup$ – Realz Slaw Nov 12 '13 at 16:33
  • 1
    $\begingroup$ Perhaps something more explicit on how to reduce it to matrix multiplication? $\endgroup$ – Realz Slaw Nov 12 '13 at 16:34
  • $\begingroup$ I don't see how you could take advantage of matrix multiplication here. $\endgroup$ – user2357112 Jan 5 at 20:22
3
$\begingroup$

Assume a complete graph containing $n$ vertices and $m$ edges.

For the all-pairs shortest path approach, this can be done using Johnson's algorithm in $O(nm + m^2 \log n)$ time, the Floyd-Warshall algorithm in $O(n^3)$ time or the tropical representation in $O(n^4)$ time.

Depending on the input size, you may be best off by just listing out each triangle, testing the inequality then reporting the outcome in $O(n^3)$ time by observing that a complete graph has $\begin{pmatrix} n \\ 3\end{pmatrix}$ triangles which can be listed using a simple brute-force algorithm.

Papers by Latapy [1], Schank and Wagner [2] offer algorithms for listing and counting triangles in complete and other types of graphs which may provide you with some more ideas.

[1] http://www-rp.lip6.fr/~latapy/Publis/triangles.pdf

[2] http://i11www.iti.uni-karlsruhe.de/extra/publications/sw-fclt-05_wea.pdf

$\endgroup$
  • $\begingroup$ The answer doesn't depend on the input size: the question states that this is a complete graph, so you have all the information you need to determine the complexity of these algorithms. All three algorithms have complexity $O(n^3)$, but the constant factor may be significantly different. $\endgroup$ – D.W. Nov 8 '13 at 19:45
  • $\begingroup$ @D.W., Since OP referred to the APSP approach, I felt appropriate to contrast their time complexities with that of the simple brute-force algorithm's to advocate the the later and not as an endorsement of the former. Nonetheless, that does not take away from the fact that the brute-force algorithm I proposed in my answer is on the order of $O(n^3)$ in terms of the number of vertices in the graph. $\endgroup$ – GEL Nov 8 '13 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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