For example, if we have a graph G = (V, E) and a subset of vertices $U \subset V$. We can set $w(e)$ where $e \in E$ to be a non-negative real number. We want to minimize the total edge weight, but make sure that for all $(u, v) \in U \times U$, $l(u, v) \geq c$, where $l(u, v)$ is the shortest path from u to v, and c is a given constant.

I suspect that this problem is NP hard, could someone come up with a polynomial solution to this?

  • $\begingroup$ The only solution is to set every edge to weight $c$. (Suppose you set $w(uv) = d < c$ for some edge $uv$: then the shortest path from $u$ to $v$ violates the constraint. Suppose you set $w(xy) = e > c$ for some edge $xy$: then there is a lower-cost solution that sets $w(xy) = c$ and satisfies all the constraints.) $\endgroup$ – j_random_hacker Mar 26 '18 at 13:53
  • $\begingroup$ Opps I think I misrepresented the question. The constraint is only for a subset of $V$, i.e. $\forall u, v \in U$, $l(u, v) > c$, where $U \subset V$ $\endgroup$ – satoru koizumi Mar 26 '18 at 14:42
  • $\begingroup$ In that case, I think you can set $w(uv) = c$ whenever both $u$ and $v$ are in $U$, to 0 when neither is in $U$, and to $c/2$ whenever exactly one of them (say, $u$) is in $U$ and the other is not, but is on some path between two vertices in $U$. Setting these edges to $c/2$ is safe, since any path between two $U$-vertices must cross at least 2 such edges. $\endgroup$ – j_random_hacker Mar 26 '18 at 15:11
  • $\begingroup$ Can $u$ and $v$ be the same? $\endgroup$ – xskxzr Mar 29 '18 at 7:04

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.