Let $G(V,E)$ be a graph and each edge e∈E has a positive length $\ell_e$. The radius of the graph is $rad(G)=\min_{v∈V}\max_{u∈V}d(u,v)$ where $d(u,v)$ stands for the shortest path between $v$ and $u.$

Now let we are allowed to increase the edge lengths by total increasing equal to B so that the radius increases as much as possible.

1-What is the complexity of this problem? Is this problem NP-hard?

2- Which problem is suitable for reduction?

  • $\begingroup$ Cross-posted: cstheory.stackexchange.com/q/40364/5038, cs.stackexchange.com/q/89313/755. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$ – D.W. Mar 14 '18 at 16:06
  • $\begingroup$ When you posted this on CSTheory.SE, I provided feedback and suggested that you edit the question to provide additional context and to show us what you've tried. Now I see that you have copy-pasted the identical question here, with no attempt to address or respond to that feedback, and no indication that you've already posted it on CSTheory.SE. That makes me wonder what is going on. I suppose I better repeat that feedback here, too. $\endgroup$ – D.W. Mar 14 '18 at 16:09
  • $\begingroup$ Please edit the question to provide additional context. Where did you encounter this problem? For example, did you run across this as an exercise or in some other source? If so, please credit the source. Did you encounter it in your research? If so, please provide the surrounding motivation / context. You should try all the obvious approaches before asking here, and show us in the question what approaches you've already tried and what useful information you can provide. What NP-complete problems have you already tried reducing from? You should try to find a reduction yourself before asking. $\endgroup$ – D.W. Mar 14 '18 at 16:10

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.