Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 8 down vote favorite
2

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.

share|improve this question
So, if $\mu=\Theta(|V|^{\epsilon})$, you want $\mu' = O(|V|^{\delta})$ for some $\delta < \epsilon$? – Neal Young Dec 12 '12 at 2:46
3  
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$. – Yury Dec 12 '12 at 2:49
@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. – Neal Young Dec 12 '12 at 3:06
@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! – Rachit Dec 12 '12 at 15:41
1  
@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. – Sasho Nikolov Dec 12 '12 at 19:47
show 3 more comments

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.