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 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}$ ?

My thoughts: consider, out of all assignments which satisfy the constraints and have 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}$, the one which minimizes the total sum of edge weights. Assume towards contradiction that for the assignment (*) that there exists a vertex pair in $ R \times R$ s.t. for all paths between these vertices all paths are strictly larger than the required constraint. and i'm hoping this yields a contradiction.

$\endgroup$
  • $\begingroup$ I am sorry for the confusion again. Francois in both of your examples you mention it is not possible to find any assignment which satisfies all of the constraints and still has at least one path for which the sum of weights on that path equals the requirement. I am only interested in the case when I am guaranteed that a possible assignment exists. I will edit the question. $\endgroup$ – user3494047 Aug 18 '15 at 17:16
  • $\begingroup$ If $V=R$, then the problem is trivial as there is an unique mimimal assignment with $e_{a,b}$ = $c_{a,b}$ for all $a,b \in V$ (If applying shortest distance algorithm to adjacency matrix, does not change the matrix, then all paths from a to b have a weight at least $c_{a,b}$. Without $R \subset V$, it is more complicated. $\endgroup$ – Tushar Aug 18 '15 at 19:47
  • $\begingroup$ Yes, you're right the hard/interesting case is $R \subset V$ $\endgroup$ – user3494047 Aug 19 '15 at 15:00

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.