Complexity of computing the average distance of a graph

Question

Let $\rm{ad}(G)$ be the average distance of a connected graph $G.$

One way to compute $\rm{ad}(G)$ is by summing up the elements of $D(G),$ the distance matrix of $G$ and scaling the sum appropriately.

If the output graph is a tree then it is known that the average distance can be computed in linear time (See B.Mohar, T.Pisanski - How to compute the Wiener index of a graph). There appears to be fast algorithms for graphs with bounded tree width as well.

An interesting question therefore is, whether it helps to know $D(G).$ In other words

Is it possible to compute $\rm{ad}(G)$ in sub-quadratic time?

What I am interested in knowing is if there is a theoretical lower bound as to why this would not be possible.

Answer 1

Computing ad(G) in $O(n^{2-\delta})$ time for constant $\delta>0$ even in graphs with $\tilde{O}(n)$ edges and $n$ vertices would imply that the Strong Exponential Time Hypothesis (SETH) is false. (SETH was defined by Impagliazzo, Paturi and Zane'01 and implies that CNF-SAT on $n$ variables does not have $O(2^{(1-\varepsilon)n})$ time algorithms.)

To prove this, note that we recently proved in (Fast approximation algorithms for the diameter and radius of sparse graphs, Liam Roditty, V. Vassilevska Williams. STOC'13.) that if one can distinguish between graphs of diameter 2 and 3 in subquadratic time, then SETH is false. The proof goes via a reduction from CNF-SAT. The same reduction can be used to show that computing ad(G) in subquadratic time shows that SETH is false, as the average distance in the graphs in the reduction would be $2-M/{N\choose 2}$ (where $N$ and $M$ are the number of nodes and edges in the reduction instance) if the CNF-SAT instance is not satisfiable, and more than that if there is a satisfying assignment.