Given a weighted undirected graph $G = (V, E)$ with maximum degree $\mu$ and with positive edge weights, is it possible to construct another graph $H = (V \cup V', E')$ with maximum degree $\mu' = o(\mu)$ (ignoring poly-log factors) such that the following two conditions are satisfied: (1) the exact distance between each pair of vertices $u, v$ remains unchanged; and (2) each edge in $H$ has a positive weight?

Has this problem been studied? Does this problem have a name? Are there any known lower and/or upper bounds on $\mu'$? Are there efficient algorithms to construct, if at all possible, such a graph $H$? What if I am also interested in the poly-log factors?

Do the answer to any of the above questions change if we consider the special case of unweighted graphs?

Clearly, the problem is of interest only if $\mu = \Omega(|V|^{\varepsilon})$ for some $\varepsilon > 0$. Also, note that the problem is extremely trivial if we do not require the second condition. Also, assume that $G$ is a connected graph.

  • $\begingroup$ So, if $\mu=\Theta(|V|^{\epsilon})$, you want $\mu' = O(|V|^{\delta})$ for some $\delta < \epsilon$? $\endgroup$ – Neal Young Dec 12 '12 at 2:46
  • 4
    $\begingroup$ Let $G$ be a star with $n$ edges in which each edge has weight/length $1$. There is no graph $G'$ s.t. $d_G(u,v) = d_{G'}(u,v)$ for every $u,v\in V(G)$ and $\mu' < \mu = n$. $\endgroup$ – Yury Dec 12 '12 at 2:49
  • $\begingroup$ @Rachit, to be clear, by "positive" you mean strictly positive, right? (Otherwise you can root a binary tree around each vertex or some such..?) If so I agree with Yuri's example. $\endgroup$ – Neal Young Dec 12 '12 at 3:06
  • $\begingroup$ @Yury --- haha! I should have thought about it! I guess your answer generalizes to graphs with any edge density. In particular, we can have a star graph attached to one single node and then the answer to my question should be in negative (though I haven't proved it formally; will be very happy to be proved wrong). Interesting! $\endgroup$ – Rachit Dec 12 '12 at 15:41
  • 1
    $\begingroup$ @Yuri If you have a star with root $x$ and leaves $y_1, \ldots y_n$, doesn't a complete binary tree with root x, leaves $y_1, \ldots y_n$ and edge lengths $1/\log n$ work? You can generalize this to any unweighted grap I think. $\endgroup$ – Sasho Nikolov Dec 12 '12 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.