3
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\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, 2018 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, 2018 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, 2018 at 15:11
  • $\begingroup$ Can $u$ and $v$ be the same? $\endgroup$
    – xskxzr
    Mar 29, 2018 at 7:04

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.