11
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Along with the bounded treewidth result you mention (Cabello and Knauer, "Algorithms for graphs of bounded treewidth via orthogonal range searching", Comp. Geom. 2009) it is known how to compute this quickly for graphs isometrically embeddable in Cartesian products of trees (which turns out to be relevant for chemical graph algorithms) — see Yeh and Gutman, "On the sum of all distances in composite graphs", Discrete Math. 1994, and Chepoi and Klavžar, "The Wiener index and the Szeged index of benzenoid systems in linear time", JCICS 1997. $\endgroup$ Apr 28 '13 at 17:16
15
$\begingroup$

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.

$\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.