<p>Computing ad(G) in $O(n^{2-\delta})$ time for constant $\delta&gt;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.)</p>

<p>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.</p>

CC BY-SA 4.0
2022-04-08T02:26:35.117Z
How do you reconcile the fact taht you cannot solve the problem in sub-quadratic time and the fact that there is a linear time algorithm to find the sum of distances in a tree?
Daniel S.
CC BY-SA 3.0
2013-04-28T18:39:42.970Z
2013-04-28T18:39:42.970Z
virgi
<p>Let $\rm{ad}(G)$ be the average distance of a connected graph $G.$ </p>

<p>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. </p>

<p>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.</p>

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

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

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

CC BY-SA 3.0
2013-04-28T17:16:53.523Z
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.
David Eppstein
<cc.complexity-theory><graph-theory><graph-algorithms>
Complexity of computing the average distance of a graph
Jernej
# Complexity of computing the average distance of a graph

(Asked by: username_0 on 2013-04-28)

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.

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2013-04-28. Score: 16 | Accepted answer

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.

> **Comments:**
> **username_3**: How do you reconcile the fact taht you cannot solve the problem in sub-quadratic time and the fact that there is a linear time algorithm to find the sum of distances in a tree?  

---

