<p>I have written up an answer, it can be found here: <a href="https://arxiv.org/abs/2104.08501" rel="nofollow noreferrer">https://arxiv.org/abs/2104.08501</a></p>
<p>The best known triangle counting algorithm runs in time <span class="math-container">$\tilde{O}(n^\omega)$</span>. I was able to retain the exponent of <span class="math-container">$n$</span> while having negative dependence on <span class="math-container">$T$</span>. In fact, the running time is <span class="math-container">$\tilde{O}_\epsilon(n^\omega/T^\delta)$</span> such that there is the is no such algorithm for any constant <span class="math-container">$\delta' &lt; \delta$</span>. In this sense, the algorithm is optimal. (One could, however, imagine an algorithm with non-constant <span class="math-container">$\delta$</span>.) The value of <span class="math-container">$\delta$</span> is <span class="math-container">$\omega - 2$</span>. This degenerates to <span class="math-container">$0$</span>, if there exists a quadratic matrix multiplication algorithm.</p>
<p>I have also done the same for sparse matrix multiplication. There, the state-of-the-art was <span class="math-container">$\tilde{O}(m^{2\omega/(\omega+1)})$</span>. I have retained the exponent while again having &quot;optimal&quot; negative dependency on <span class="math-container">$T$</span> (albeit the optimality is in the fairly weak sense mentioned above).</p>
<p>For a sketch of the algorithm, see page 5 in the paper. If you have comments, I would be very happy to hear them.</p>
<p>Here is a diagram comparing the running time to other algorithms:
<a href="https://i.sstatic.net/ei1Fm.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ei1Fm.png" alt="enter image description here" /></a></p>
<p>(I have just noticed that the diagram on the right should have log base <span class="math-container">$m$</span>, I'll fix it later)</p>
<p>The &quot;optimality&quot; lies in the fact that the blue line (my algorithm) touches the dashed red line (the lower bound). And yes, our algorithm is in fact slower than state-of-the-art for large values of <span class="math-container">$T$</span>. On that range, the optimal algorithm was in fact already known. One could probably fix that so that this algorithm is never slower than the state-of-the-art; however, the analysis is already technically non-trivial as it is now.</p>

CC BY-SA 4.0
2021-05-18T17:07:59.810Z
2021-05-18T17:07:59.810Z
user2316602
<p>One may compute the number of triangles in a graph by matrix multiplication in time <span class="math-container">$O(n^\omega)$</span>. There is also a very simple algorithm that runs in time <span class="math-container">$O(n^3/(\epsilon^2 T))$</span> (where <span class="math-container">$T$</span> is the number of triangles) for <span class="math-container">$1\pm \epsilon$</span> approximate triangle counting. It works by repeatedly sampling triplets of vertices and using those sample to estimate the number of triangles.</p>
<p>Is there anything asymptotically faster than these two algorithms? I am aware of the sublinear-time algorithms for triangle counting. However, those that I am aware of are parameterized by the number of edges and not the number of vertices. I am only interested in results parameterized by the number of vertices.</p>

CC BY-SA 4.0
2021-03-06T11:33:52.897Z
But can't you take any of those sublinear algorithms and plug in $n^2$ instead of $m$ to get an upper bound on the running time? E.g., https://arxiv.org/abs/1504.00954 will then replace your $n^3/T$ by $\min(n^2, n^3/T)$.
Clement C.
CC BY-SA 4.0
2021-03-06T11:37:02.853Z
Yes, I can indeed do that. However, the paper that you mentioned gives no improvement of over $n^3/T$ as I care about time complexity, whereas the $m$ bound in their paper is the trivial bound on *query* complexity.
user2316602
CC BY-SA 4.0
2021-03-06T11:40:11.747Z
I see. Well, their lower bound (Theorem 15 in the arXiv version) on the query complexity apparently also applies to dense graphs, so that means the time complexity will need to be at least $\min(n^2, n^3/T)$ (and so your window for time complexity improvement over $n^3/T$ is quite limited).
Clement C.
CC BY-SA 4.0
2021-03-06T11:41:08.307Z
Indeed. Actually, if $\omega = 2$, it is non-existent!
user2316602
CC BY-SA 4.0
2021-03-06T16:06:17.790Z
I think I have heard that nothing better than matrix multiplication is known even for triangle detection, but I couldn't find a reference.
Laakeri
CC BY-SA 4.0
2021-03-06T16:24:32.480Z
Yes, I agree. However, one could imagine an algorithm that runs in something like $n^\omega/T^{0.01}$
user2316602
CC BY-SA 4.0
2021-03-11T21:52:04.153Z
Using [quantum computers](https://arxiv.org/abs/1504.06987) you can go quadratically faster and with failure chance $\delta$ estimate the number of triangles in $O\left(\log(1/\delta) \sqrt{n^3/(\epsilon^2T)}\right)$ within relative error $\epsilon$.
orlp
<ds.algorithms><time-complexity><approximation>
Fastest approximate triangle counting algorithms in dense graphs
user2316602
# Fastest approximate triangle counting algorithms in dense graphs

(Asked by: username_0 on 2021-03-06)

One may compute the number of triangles in a graph by matrix multiplication in time $O(n^\omega)$. There is also a very simple algorithm that runs in time $O(n^3/(\epsilon^2 T))$ (where $T$ is the number of triangles) for $1\pm \epsilon$ approximate triangle counting. It works by repeatedly sampling triplets of vertices and using those sample to estimate the number of triangles.

Is there anything asymptotically faster than these two algorithms? I am aware of the sublinear-time algorithms for triangle counting. However, those that I am aware of are parameterized by the number of edges and not the number of vertices. I am only interested in results parameterized by the number of vertices.

**Tags:** ds.algorithms, time-complexity, approximation
> **Comments:**
> **username_1**: But can't you take any of those sublinear algorithms and plug in $n^2$ instead of $m$ to get an upper bound on the running time? E.g., https://arxiv.org/abs/1504.00954 will then replace your $n^3/T$ by $\min(n^2, n^3/T)$.  
> **username_0**: Yes, I can indeed do that. However, the paper that you mentioned gives no improvement of over $n^3/T$ as I care about time complexity, whereas the $m$ bound in their paper is the trivial bound on *query* complexity.  
> **username_1**: I see. Well, their lower bound (Theorem 15 in the arXiv version) on the query complexity apparently also applies to dense graphs, so that means the time complexity will need to be at least $\min(n^2, n^3/T)$ (and so your window for time complexity improvement over $n^3/T$ is quite limited).  
> **username_0**: Indeed. Actually, if $\omega = 2$, it is non-existent!  
> **username_2**: I think I have heard that nothing better than matrix multiplication is known even for triangle detection, but I couldn't find a reference.  
> **username_0**: Yes, I agree. However, one could imagine an algorithm that runs in something like $n^\omega/T^{0.01}$  
> **username_3**: Using [quantum computers](https://arxiv.org/abs/1504.06987) you can go quadratically faster and with failure chance $\delta$ estimate the number of triangles in $O\left(\log(1/\delta) \sqrt{n^3/(\epsilon^2T)}\right)$ within relative error $\epsilon$.  

---

## 1 answers

### Answer by username_0 on 2021-05-18. Score: 1 | Accepted answer

I have written up an answer, it can be found here: <https://arxiv.org/abs/2104.08501>

The best known triangle counting algorithm runs in time $\tilde{O}(n^\omega)$. I was able to retain the exponent of $n$ while having negative dependence on $T$. In fact, the running time is $\tilde{O}\_\epsilon(n^\omega/T^\delta)$ such that there is the is no such algorithm for any constant $\delta' < \delta$. In this sense, the algorithm is optimal. (One could, however, imagine an algorithm with non-constant $\delta$.) The value of $\delta$ is $\omega - 2$. This degenerates to $0$, if there exists a quadratic matrix multiplication algorithm.

I have also done the same for sparse matrix multiplication. There, the state-of-the-art was $\tilde{O}(m^{2\omega/(\omega+1)})$. I have retained the exponent while again having "optimal" negative dependency on $T$ (albeit the optimality is in the fairly weak sense mentioned above).

For a sketch of the algorithm, see page 5 in the paper. If you have comments, I would be very happy to hear them.

Here is a diagram comparing the running time to other algorithms:
[![enter image description here](https://i.sstatic.net/ei1Fm.png)](https://i.sstatic.net/ei1Fm.png)

(I have just noticed that the diagram on the right should have log base $m$, I'll fix it later)

The "optimality" lies in the fact that the blue line (my algorithm) touches the dashed red line (the lower bound). And yes, our algorithm is in fact slower than state-of-the-art for large values of $T$. On that range, the optimal algorithm was in fact already known. One could probably fix that so that this algorithm is never slower than the state-of-the-art; however, the analysis is already technically non-trivial as it is now.


---

