2
$\begingroup$

We have an undirected, weighted graph $G=(V, E)$ with two weight functions $W_1 : E \rightarrow \mathbb{R}^{+}$ and $W_2 : E \rightarrow \mathbb{R}^{+}$ such that for every $e \in E$ we have $W_1(e) > W_2(e)$.

The length of a walk $\sigma$ is calculated in such a way that for every edge $e \in E$, for the first appearance of $e$ in $\sigma$ we calculate the weight of $e$ by $W_1(e)$, and for reminding appearances of $e$ in $\sigma$ we calculate the weight of $e$ by $W_2(e)$.

The goal is to find the shortest walk from $u$ to $v$ through $w$. Is this problem $\mathsf{NP}$-hard? If not, how can we find such a walk?

$\endgroup$
6
  • $\begingroup$ Since this problem is not a decision problem, it is not in $\mathsf{NP}$. Perhaps you want to consider the decision version of the problem? $\endgroup$
    – Nathaniel
    Commented Nov 28, 2021 at 9:16
  • $\begingroup$ I apologize, the mistake was corrected. $\endgroup$
    – R.hatam
    Commented Nov 28, 2021 at 9:25
  • $\begingroup$ The shortest walk from $u$ to $v$ via $w$ consists of a shortest walk from $u$ to $w$ together with a shortest walk from $w$ to $v$. $\endgroup$ Commented Nov 28, 2021 at 15:31
  • $\begingroup$ If we choose a bit longer walk from u to w, then, might we can use the lightened edges more efficiently. So I think that the greedy algorithm can not find an optimal walk. $\endgroup$
    – R.hatam
    Commented Nov 28, 2021 at 19:49
  • $\begingroup$ cs.stackexchange.com/q/146174/755 $\endgroup$
    – D.W.
    Commented Nov 29, 2021 at 0:24

1 Answer 1

1
$\begingroup$

The shortest walk must have the form

u
 \
  t<->w
 /
v

where the edges in each arrow are disjoint. To see this, suppose in the shortest walk, we go through nodes $u_1'=u,\ldots,u_{k'}',u_1,\ldots,u_k=w$ from $u$ to $w$, go through nodes $v_1=w,\ldots,v_l,v_1',\ldots,v_{l'}'=v$ from $w$ to $v$, where $v_1',\ldots,v_{l'}' \notin \{u_1',\ldots,u_{k'}',u_1,\ldots,u_k\}$, and $v_l=u_1$, like the following graph:

                  u    (u_1,...,u_k)
 (u_1',...,u_{k'}')\        /\
                    u_1(v_l)  w       The walk (u_1,...,u_k) may overlap with (v_1,...,v_l)
 (v_1',...,v_{l'}')/        \/
                  v    (v_1,...,v_l)

Now suppose edges $e_1,\ldots,e_h$ are shown in both the walk $(u_1,...,u_k)$ and the walk $(v_1,\ldots,v_l)$, and the remaining edges in both walks are $f_1,\ldots,f_p$ and $g_1,\ldots,g_q$ respectively. Then the cost of the walk $(u_1,...,u_k=v_1,\ldots,v_l)$ is \begin{align*} &\sum_{i=1}^h (W_1(e_i)+W_2(e_i))+\sum_{i=1}^pW_1(f_i)+\sum_{i=1}^qW_1(g_i)\\ \ge{}&\sum_{i=1}^h (W_1(e_i)+W_2(e_i))+\frac{1}{2}\left(\sum_{i=1}^p(W_1(f_i)+W_2(f_i))+\sum_{i=1}^q(W_1(g_i)+W_2(g_i))\right). \end{align*} That is, the average cost of the walk $(u_1,\ldots,u_k,\ldots,u_1)$ and the walk $(v_l,\ldots,v_1,\ldots,v_l)$ is no more than that of the walk $(u_1,...,u_k=v_1,\ldots,v_l)$. So the shortest walk must have the form shown in the first figure.

Now you can try every node as $t$ to compute the optimal walk from $u$ to $w$ to $v$. This is a polynomial-time algorithm.

$\endgroup$

Your Answer

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

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