MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## A generalization of the triangle counting problem for simple weighted graphs

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.

-
How are you computing complexity? Is arithmetic (including factoring) O(1)? – Igor Rivin Aug 10 at 15:25
If this assumption allows for an answer then we can suppose arithmetic operations are carried in $O(1)$ although I am afraid that in the most general case this is not so. I would expect the edge weights to be bounded by a polynomial in $n$ though. – Jernej Aug 10 at 15:41
While not the best idea, you could consider doing computations mod the square of some chosen primes. Alternatively, you could perform some modification of matrix multiplication by zeroing out invalid pairs, but I don't see that as being of subcubic complexity. Gerhard "Ask Me About System Design" Paseman, 2012.08.10 – Gerhard Paseman Aug 10 at 17:42
W@Gerhard: why the square? – Igor Rivin Aug 10 at 18:43
The hope (unfounded, unfortunately), is that the weights are all square free, that they consist of few prime factors, that their products can be stored somehow, and that computing modulo pp will zero out the invalid pairs for some p. It may not work, but perhaps some variation might. Gerhard "That's Why It's A Comment" Paseman, 2012.08.10 – Gerhard Paseman Aug 10 at 22:14
show 1 more comment

 "two coloring a graph with few violations" is the min uncut problem. it is NP-hard to solve exactly and can be approximated to within $O(\sqrt{\log n})$, see cs.princeton.edu/courses/archive/spr05/cos598B/…. the approximation requires solving an SDP but maybe can be made to run faster with primal-dual techniques, as was done for sparsest cut – Sasho Nikolov Aug 26 at 3:34