3
$\begingroup$

We are given a graph $G = (V,E)$ and we need to find an assignment of non-negative edge weights (You must give every edge a non-negative weight). We are also given a set $R\subseteq V$ and mapping $c_{a,b}: R\times R \rightarrow \mathbb{R^+}$ where $\mathbb{R}^+$ is all positive ($> 0$) reals ($c_{a,b} = c_{b,a}$ for all $a,b$ and $c_{a,a} = 0$ for all $a$ ). Our edge weight assignment is constrained by the requirement that for all vertex pairs $(a,b)\in R\times R$, all paths from $a$ to $b$ need to have at least weight $c_{a,b}$ where the weight of the path is the sum of all edge weights on that path.

Now assume that there exists an assignment that satisfies all of the constraints and such that for all vertex pairs $(a,b)\in R \times R $ there exists at least one path from $a$ to $b$ whose weight is exactly equal to $c_{a,b}$.

Now consider the assignment of edge weights (*) that satisfies the constraints and minimizes the total sum of edge weights. Is it true that for all vertex pairs $(a,b)\in R \times R$ there will exist at least one path from $a$ to $b$ whose weight is exactly equal to $c_{a,b}$ ?

$\endgroup$
1
$\begingroup$

Yes.

Consider an exact assignment as described in your second paragraph.

If any edge has a weight $w_{a,b} > c_{a,b}$ there must be an indirect path with total path weight $c_{a,b}$, This means the direct edge $ab$ will not be part of any minimal path. We can lower the weight to $w_{a,b} = c_{a,b}$ without changing this.

Therefore, if an exact assignment exists, $w_{a,b} = c_{a,b}$ (for all a,b) will be an exact assignment.

It is clear that this is the unique assignment with minimal total weight.

$\endgroup$
  • $\begingroup$ I completely rewrote my answer, the comments from Aug 27 are not relevant. $\endgroup$ – Stig Hemmer Aug 31 '15 at 18:08
  • $\begingroup$ Thanks Stig but I think it doesn't work. What if in the given graph G there is no edge between a and b? G is a graph with some predetermined edges, it is not necessarily a complete graph. I agree that for this problem, if there is an edge between a and b then necessarily its weight must be equal to $c_{a,b}$, but it might not have an edge there. Also I don't follow the logic of "If any edge has weight $w_{a,b} > c_{a,b}$ there must be an indirect path with total path weight $c_{a,b}$." I think the logic should be: then there must be an indirect path with total weight $\geq c_{a,b}$ $\endgroup$ – user3494047 Sep 1 '15 at 7:49
  • $\begingroup$ The assumtion was that "there exists at least one path from a to b whose weight is exactly equal to $c_{a,b}$ ." If this is not the direct edge, it must be an indirect path. $\endgroup$ – Stig Hemmer Sep 1 '15 at 8:07
  • $\begingroup$ The assumption is not that "there exists at least one path...". The assumption is that there exists an assignment such that satisfies the constraints and there exists at least one path... . The assignment which you are assuming exists and the assignment which minimizes the total sum of edge weights are not the necessarily the same assignment. If you prove they are necessarily the same assignment then you have solved my question (even though this definitely not the only way to solve the question). $\endgroup$ – user3494047 Sep 1 '15 at 11:43

Your Answer

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

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