Given an undirected graph

G(V,E), how fast can we detect if

G is triangle-free ? Cubic time is obvious. Let

A be the adjacency matrix of G. We can detect triangle-freeness of

G in the same complexity as multiplying two boolean matrices (

AxA) (duh !!). This simple algorithm is the

best known !! In other words, following is the open problem :

- Is testing triangle-freeness as difficult as the Boolean multiplication of two |V| x |V | matrices?

A recent paper

[1] addressess this problem partially. In a related note, the complexity of all pairs shortest paths (APSP) is still

unresolved. Is APSP (for undirected graphs) as difficult as the Boolean multiplication of two |V| x |V | matrices?

[1] 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.

## No comments:

Post a Comment