Complejidad de contar el número de triángulos de un gráfico

Question

El trivial enfoque de contar el número de triángulos en un simple gráfico de $G$ orden $n$ es comprobar que todos los triples $(x,y,z) \in {V(G)\choose 3}$ si $x,y,z$ forma un triángulo.

Este procedimiento nos da la complejidad algorítmica de $O(n^3)$.

Es bien sabido que si $A$ es la matriz de adyacencia de $G$, entonces el número de triángulos en $G$ $tr(A^3)/6.$

Desde la multiplicación de la matriz puede ser calculado en tiempo de $O(n^{2.37})$ es natural preguntarse:

Hay alguna (conocida) método más rápido para calcular el número de triángulos de una gráfica?

Answer 1

Permítanme citar este documento a partir de 2007 (algoritmos Prácticos para el triángulo de cálculos muy grandes (sparse (ley de potencia)) gráficos por Matthieu Latapy):

El más rápido algoritmo conocido para encontrar y contar los triángulos se basa en el rápido de la matriz producto, y tiene un $\mathcal{O}(n^\omega)$ tiempo complejidad, donde $\omega < 2.376$ es la rapidez de la matriz producto exponente. Este enfoque, sin embargo, conduce a una $\theta(n^2)$ espacio de la complejidad.

Hay algunas mejoras para las gráficas o si desea la lista de los triángulos que se muestran en el documento.