3
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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., arxiv.org/abs/1504.00954 will then replace your $n^3/T$ by $\min(n^2, n^3/T)$. $\endgroup$
    – Clement C.
    Mar 6 at 11:33
  • 1
    $\begingroup$ 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). $\endgroup$
    – Clement C.
    Mar 6 at 11:40
  • 1
    $\begingroup$ I think I have heard that nothing better than matrix multiplication is known even for triangle detection, but I couldn't find a reference. $\endgroup$
    – Laakeri
    Mar 6 at 16:06
  • 1
    $\begingroup$ Yes, I agree. However, one could imagine an algorithm that runs in something like $n^\omega/T^{0.01}$ $\endgroup$ Mar 6 at 16:24
  • 1
    $\begingroup$ Using quantum computers 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$. $\endgroup$
    – orlp
    Mar 11 at 21:52
1
$\begingroup$

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.