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, 2012 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, 2012 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, 2012 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, 2012 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$ Dec 12, 2012 at 19:47


Your Answer

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

Browse other questions tagged or ask your own question.