Complexidade da computação à distância média de um gráfico

Deixe $\rm{ad}(G)$ é a distância média de um gráfico conectado $G.$

Uma maneira de calcular $\rm{ad}(G)$ é somando os elementos de $D(G),$ a matriz de distância de $G$ e escalando a soma adequadamente.

Se o gráfico de saída for uma árvore, sabe-se que a distância média pode ser calculada em tempo linear (consulte B.Mohar, T.Pisanski - Como calcular o índice de Wiener de um gráfico). Parece haver algoritmos rápidos para gráficos com largura de árvore limitada também.

Uma pergunta interessante, portanto, é se isso ajuda a conhecer $D(G).$ Em outras palavras

É possível calcular $\rm{ad}(G)$ em tempo sub-quadrático?

O que eu estou interessado em saber é se existe um limite inferior teórico de por que isso não seria possível.

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

Juntamente com o resultado da largura da árvore delimitada que você menciona (Cabello e Knauer, "Algoritmos para gráficos de largura da árvore delimitada por meio de pesquisa de faixa ortogonal", Comp. Geom. 2009), é conhecido como calcular isso rapidamente para gráficos isometricamente incorporáveis em produtos cartesianos de árvores ( que acaba sendo relevante para algoritmos de gráficos químicos) - consulte Yeh e Gutman, "Sobre a soma de todas as distâncias em gráficos compostos", Matemática Discreta. 1994, e Chepoi e Klavžar, "O índice Wiener e o índice Szeged de sistemas benzenoides em tempo linear", JCICS 1997.

David Eppstein

Respostas:

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

Para provar isso, observe que recentemente provamos em (Algoritmos de aproximação rápida para o diâmetro e o raio de gráficos esparsos, Liam Roditty, V. Vassilevska Williams. STOC'13.) Que se é possível distinguir entre gráficos de diâmetro 2 e 3 em subquadrática tempo, então SETH é falso. A prova passa por uma redução do CNF-SAT. A mesma redução pode ser usada para mostrar que o anúncio de computação (G) em tempo subquadrático mostra que SETH é falso, pois a distância média nos gráficos na redução seria (onde e são o número de nós e arestas na instância de redução) se a instância CNF-SAT não for satisfatória e mais que isso se houver uma atribuição satisfatória. $2-M/{N\choose 2}$ $N$ $M$

virgi
fonte