Today’s post is about the following question and related problems.
Given an undirected graph , how fast can we detect if is triangle-free ?
Cubic time is obvious. A faster algorithm computes the square of the adjacency matrix of and runs in time , where is the matrix multiplication exponent. This simple algorithm is the best known !!
Is testing triangle-freeness as hard as the Boolean multiplication of two |V| x |V | matrices?
Look at [AKKR’06] for recent results. A related problem is all pairs shortest paths (APSP). This is a fundamental graph problem and its exact complexity is still open.
Is APSP (for undirected graphs) as difficult as the Boolean multiplication of two |V| x |V | matrices?
These problems are tightly related to matrix multiplication, whose complexity is also open. The best value of is 2.376. At Barriers Workshop, Chris Umans presented an exciting group-theoretic approach [CU’03, CKSU’05] to improving . Using their techniques, the best value of they achieved is 2.41. In their paper, they made two conjectures, one combinatorial and the other algebraic. Either one would imply that the exponent of matrix multiplication is 2.
Is ?
References :
- [AKKR’06] N. Alon, T. Kaufman, M. Krivelevich, and D. Ron. Testing triangle-freeness in general graphs. Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 279–-288, 2006.
- [CKSU’05] Henry Cohn, Robert D. Kleinberg, Balázs Szegedy, Christopher Umans. Group-theoretic Algorithms for Matrix Multiplication. FOCS 2005: 379-388
- [CU’03] Henry Cohn, Christopher Umans: A Group-Theoretic Approach to Fast Matrix Multiplication. FOCS 2003: 438-449
I expect the lower bound to be
n^2 \log n
totally by historical analogy with integer multiplication.
[AKKR 06] deals with testing triangle-freeness in the property testing model, that is distinguishing triangle-free graphs from those far from triangle-free. I don’t believe any connection to matrix multiplication is known in this setting.