One nice identity is that $$\operatorname{tr}(A^3)/6$$ counts the number of triangles of a graph with adjacency matrix $A$. It also implies that triangle counting in a graph can be performed in sub-cubic time.
Consider now the following variant of the triangle counting problem.
Given is a simple graph $G$ of order $n$ with a weight function defined on the edge set $$w:E(G) \mapsto \mathbb{Z}^{+}.$$ A triangle of $G$ with edges $e_1$, $e_2$, $e_3$ is said to be valid if the edge weights are pairwise coprime. That is $$\gcd(w(e_1),w(e_2)) = \gcd(w(e_1),w(e_3)) = \gcd(w(e_2),w(e_3)) = 1.$$
What am I wondering is the following:
Can you count the number of valid triangles of a weighted graph $G$ in sub-cubic time?
Note that if all edge weights are 1, we are dealing with the classical triangle counting problem.
Intuitively, I believe that this is not possible since for a fixed vertex $v$ one has to check the gcd for $O(n^2)$ neighbours of $v$. But, then again, the matrix multiplication trick is also counter-intuitive in its own way.
So I would like to hear a more refined answer why this cannot be achieved or perhaps how it can be.
Best Answer
Are you aware of the topic "Fine-grained complexity"? There are some related topics that you may find interesting:
It is a conjecture that no "COMBINATORIAL" algorithm would solve matrix multiplication faster that $\theta (n^3)$. The consequence of this conjecture is that similar problems have sub-cubic time algorithm only if they use fast matrix multiplication. (Therefore, some answers trying to find a combinatorial triangle finding are doomed to fail!)
Some problems like finding a negative triangle in a (dense) graph is conjectured to have no sub cubic algorithms (because then the problem All-Pairs Shortest Paths would have sub-cubic algorithm, and no one found such an algorithm over 30 years of heavy research). So you may try to reduce APSP to your problem and prove that its does not have a sub-cubic time algorithm.