0
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ 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)$? $\endgroup$ May 2, 2023 at 2:59

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks! Didn't think to use the triangle inequality here. $\endgroup$
    – Gabi G
    May 2, 2023 at 6:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.