# Universal lower bound of the multi message problem

The multi message problem is: Let there be an undirected graph $$G = (V,E)$$ with $$n$$ vertices, and let $$r \in G$$. The algorithm sends a message $$M_i$$ of size $$\Omega(\log(n))$$ to each vertex $$v_i$$ using the shortest path.

The cost of the problem is the sum of route length multiplied by the message size. Let denote the cost of the problem as $$Comm(MM)$$, when a graph $$G$$ is picked then $$Comm(MM,G)$$, and when a vertex $$r$$ of $$G$$ is picked then $$Comm(MM,G, r)$$.

I want to prove or disprove the following: For every Graph $$G$$, there exists a vertex $$r$$ in $$G$$ such that $$Comm(MM,G, r) = \Omega(nd\log(n))$$, where $$D$$ is the graph diameter.

My initial approach was to try and prove this claim, and I intended to use the central vertex of each graph. However, it didn't lead me anywhere.

Then, I did the following. There are vertices $$u, w \in V$$ such that $$dist(u,w) = D$$. Let's denote $$w = v_{D}$$. So there is a vertex $$v_{D-1}$$ such that $$dist(u,v_{D-1}) = D - 1$$, and vertex $$v_{D-2}$$ such that $$dist(u,v_{D-2}) = D - 2$$, and so on until $$v_1$$. But here I again got stuck, because I still don't know anything about the rest of the $$n-D$$ vertices.

I'm still not sure if I should prove or disprove this claim.

Help would be appreciated!

• How is the message size relevant? Isn't an equivalent statement is that for every graph there is a vertex for which the sum of its distances to other vertices is $\Omega(n d)$? May 2, 2023 at 2:59

The claim is correct. Let there be two vertices such that $$\text{dist}(u, w) = D$$. Note that for every vertex $$v$$ we know $$\text{dist}(u, v) + \text{dist}(v, w) \geq D$$ due to the triangle inequality. If we will sum this over all vertices $$v$$ we get $$\sum_{v}{\text{dist}(u, v)} + \sum_v{\text{dist}(v, w)} \geq nD$$ This means at least one of $$\sum_{v}{\text{dist}(u, v)}$$ or $$\sum_v{\text{dist}(v, w)}$$ is greater than $$\frac{nD}2$$, and if you'll choose that one as $$r$$ you'll get a cost of $$\Omega(nD \log(n))$$.