2
$\begingroup$

The Triangle Finding problem (TF) in Graph Theory was shown by Itai and Rodeh in 1977 [1] to be solvable as fast$^1$ as Boolean Matrix Multiplication (BMM, Matrix Multiplication over $\{0, 1\}$ with AND for $\times$ and OR for $+$). It seems to be common knowledge that BMM itself is solvable as fast as ordinary Matrix Multiplication (MM), so basically TF can be solved at least in $O(n^{ω'+o(1)})$, where $ω'$ means the best known MM exponent.

Question: Has this complexity always been the best we've been able to do on TF? Has there ever been an algorithm for TF which was faster than the then-best MM algorithm?

I've done some research here and there, and the closest I got to the answer was V Williams and Williams's 2018 paper [2], which briefly noted that TF is $O(n^{2.38})$ (which is the best MM complexity as of 2021 [3]), and cited [1] as their reference (the note is at the end of page 2 on my PDF).

I'm mostly interested in algorithms which do not depend on the density of the graph; in other words, I appreciate answers providing orders which are functions of $m$ (both for learning more, and for enriching the site), but I'm afraid they're not quite helpful to me as of now.


$^1$ When I say fast, I mean fast in the sense of time-complexity.

[1] A. Itai and M. Rodeh, “Finding a Minimum Circuit in a Graph,” in Proceedings of the Ninth Annual ACM Symposium on Theory of Computing, in STOC ’77. New York, NY, USA: Association for Computing Machinery, 1977, pp. 1–10. doi: 10.1145/800105.803390.

[2] V. V Williams and R. Williams, “Subcubic Equivalences between Path, Matrix and Triangle Problems,” in 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 2010, pp. 645–654. doi: 10.1109/FOCS.2010.67.

[3] J. Alman and V. V. Williams, “A Refined Laser Method and Faster Matrix Multiplication,” in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021, pp. 522–539. doi: 10.1137/1.9781611976465.32.

$\endgroup$

0

Your Answer

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