Return to Question

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.

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.

One nice identity is $$tr(A^3)/6$$ which counts the number of triangles of a graph represented with adjacency matrix $A.$ It also implies that triangle counting can be performed in subcubic 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 subcubic 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.

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.

One nice identity is $$tr(A^3)/6$$ which counts the number of triangles of a graph represented with adjacency matrix $A.$ It also implies that triangle counting can be performed in subcubic time.

Consider now the following variant of the triangle counting problem.

Given is a simple graph $G$ 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 subcubic 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.

One nice identity is $$tr(A^3)/6$$ which counts the number of triangles of a graph represented with adjacency matrix $A.$ It also implies that triangle counting can be performed in subcubic 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 subcubic 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.