19
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ How are you computing complexity? Is arithmetic (including factoring) O(1)? $\endgroup$
    – Igor Rivin
    Commented Aug 10, 2012 at 15:25
  • $\begingroup$ 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. $\endgroup$
    – Jernej
    Commented Aug 10, 2012 at 15:41
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Aug 10, 2012 at 17:42
  • $\begingroup$ W@Gerhard: why the square? $\endgroup$
    – Igor Rivin
    Commented Aug 10, 2012 at 18:43
  • 3
    $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Aug 10, 2012 at 22:14

3 Answers 3

Reset to default
1
$\begingroup$

Are you aware of the topic "Fine-grained complexity"? There are some related topics that you may find interesting:

  1. 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!)

  2. 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.

Improve this answer
$\endgroup$
0
$\begingroup$

Here is a dumb idea. Consider processing the graph one prime at a time. This might be removing all edges with weight a multiple of p, or keeping only those that are. Do the trace computation for each induced graph and collate the results. (How? Beats me. I'm throwing out ideas with no guarantee that they will make sense, much less work.)

Here is another dumb idea, which may be good for graphs with low degree. Pick an edge. Find all valid incident edges. Count the number of triangles containing that edge. Throw out that edge. Repeat until no more triangles exist. (Perhaps the graph is not different in number of edges from a bipartite graph, in which case significant run time savings can be achieved. However, I do not know the literature on two coloring a graph with few violations.)

Gerhard "Need Good Ideas? Start Dumb" Paseman, 2012.08.11

Improve this answer
$\endgroup$
1
  • $\begingroup$ "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/lecture8.pdf. the approximation requires solving an SDP but maybe can be made to run faster with primal-dual techniques, as was done for sparsest cut $\endgroup$
    – Sasho Nikolov
    Commented Aug 26, 2012 at 3:34
0
$\begingroup$

Number of coprime triangles equals $\sum \mu(k) T_k$, where $T_k$ is the number of triangles in the graph of edges with weight divisible by $k$. It may be useful if these graphs become sparse for large $k$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .