Complejidad de calcular la distancia promedio de un gráfico

Deja $\rm{ad}(G)$ sea la distancia media de un gráfico conectado $G.$

Una forma de calcular $\rm{ad}(G)$ es sumar los elementos de $D(G),$ la matriz de distancia de $G$ y escalar la suma adecuadamente.

Si el gráfico de salida es un árbol, entonces se sabe que la distancia promedio se puede calcular en tiempo lineal (Ver B.Mohar, T.Pisanski - Cómo calcular el índice Wiener de un gráfico). Parece que también existen algoritmos rápidos para gráficos con ancho de árbol acotado.

Por lo tanto, una pregunta interesante es si es útil saber $D(G).$ En otras palabras

¿Es posible calcular $\rm{ad}(G)$ en tiempo subcuadrático?

Lo que me interesa saber es si hay un límite inferior teórico de por qué esto no sería posible.

cc.complexity-theory graph-theory graph-algorithms Jernej
fuente

Junto con el resultado del ancho de árbol limitado que mencionas (Cabello y Knauer, "Algoritmos para gráficos de ancho de árbol limitado mediante búsqueda de rango ortogonal", Comp. Geom. 2009) se sabe cómo calcular esto rápidamente para gráficos que se pueden insertar isométricamente en productos cartesianos de árboles ( que resulta relevante para los algoritmos de gráficos químicos) - vea Yeh y Gutman, "Sobre la suma de todas las distancias en gráficos compuestos", Matemática discreta. 1994, y Chepoi y Klavžar, "El índice Wiener y el índice Szeged de los sistemas benzenoides en tiempo lineal", JCICS 1997.

David Eppstein

Respuestas:

$O(n^{2-\delta})$ $\delta>0$ $\tilde{O}(n)$ $n$ $n$ $O(2^{(1-\varepsilon)n})$

Para probar esto, tenga en cuenta que recientemente probamos en (Algoritmos de aproximación rápida para el diámetro y el radio de gráficos dispersos, Liam Roditty, V. Vassilevska Williams. STOC'13.) Que si uno puede distinguir entre gráficos de diámetro 2 y 3 en subcuadráticos tiempo, entonces SETH es falso. La prueba pasa por una reducción de CNF-SAT. La misma reducción se puede usar para mostrar que el anuncio informático (G) en tiempo subcuadrático muestra que SETH es falso, ya que la distancia promedio en los gráficos en la reducción sería (donde y son el número de nodos y aristas en la instancia de reducción) si la instancia CNF-SAT no es satisfactoria, y más que eso si hay una asignación satisfactoria. $2-M/{N\choose 2}$ $N$ $M$

virgi
fuente