1
$\begingroup$

I am stuck at the following exercise:

Consider a directed graph $G = (V, A)$ with start vertex $s ∈ V$, target vertex $t \in V$ and weights $w_{ij} \in \mathbb{R}$ for each arc $(i, j)\in A$. For any $i \in V$ let further be $\pi_i \in \mathbb{R}$ be the so-called potential of $i$. The potential difference $\tau_{ij} = \pi_i − \pi_j$ is called the tension of the arc $(i, j)$ with respect to the potential vector $\pi$. Finally, let $\mathcal{P}$ denote the set of all directed paths from $s$ to $t$.

Now consider the following LP $(P)$: \begin{align} \max& \sum_{(i,j) \in P} \tau_{ij}\\ s.t. & \qquad P \in \mathcal{P} \\ & \qquad \tau_{ij} = \pi_i - \pi_j \text{ for all $(i,j) \in A$}\\ & \qquad \tau_{ij} \le w_{ij} \text{ for all $(i,j) \in A$}\\ & \qquad \pi_i \in \mathbb{R} \text{ for all $i \in V$} \end{align}

If $P^\ast$ is a path for which the maximum in $\mathcal{P}$ is achieved, the value $\sum_{(i,j) \in P^\ast} \tau_{ij}$ is referred to as maximum tension between $s$ and $t$.

Prove that under the assumption that an $s$-$t$ shortest path exists with respect to the arc weights $w_{ij}$, the length of a shortest $s$-$t$ path equals the maximum tension between $s$ and $t$.

If I am not mistaken we have by the definition of $\tau_{ij}$ that $\sum_{(i,j) \in P} \tau_{ij} = \pi_s-\pi_t$, so the maximal tension is constant for all $P \in \mathcal{P}$. Could you please tell me what I am misunderstanding?

Remark: I know that this is supposed to be the dual of the shortest path problem, but I am supposed to do this directly.

$\endgroup$
1
  • 2
    $\begingroup$ We require you to credit the original source of all copied material: cs.stackexchange.com/help/referencing. Please revise your question accordingly. $\endgroup$
    – D.W.
    Oct 28 at 22:44

1 Answer 1

1
$\begingroup$

The statement in the exercise, "If $P^\ast$ is a path for which the maximum in $\mathcal{P}$ is achieved, the value $\sum_{(i,j) \in P^\ast} \tau_{ij}$ is referred to as maximum tension between $s$ and $t$." is indeed quite confusing.

As you have pointed out, given $i\to\pi_i$ for all $i\in V$ and $\tau_{ij}=\pi_i-\pi_j$, we know the sum $\sum_{(i,j) \in P} \tau_{ij} = \pi_s-\pi_t$ does not depend on the choice of $P \in \mathcal{P}$.

Here is an equivalent but clearer definition of the maximum tension.

Consider a directed graph $G = (V, A)$ with start vertex $s ∈ V$, target vertex $t ∈ V$ and weights $w_{ij} \in \mathbb{R}$ for each arc $(i, j)\in A$. Assume there is a path from $s$ to $t$. Then the maximum tension of $(G, s, t, w)$ is the optimal value of the objective function of the the following linear program. When $G$ and $w$ are understood, we also call it the maximum tension from $s$ to $t$.

$$\begin{array}{rl} \max&\pi_s-\pi_t\\ s.t. & \pi_i - \pi_j \le w_{ij} \text{ for all }(i,j) \in A\\ & \pi_i \in \mathbb{R} \text{ for all $i \in V$} \end{array}$$

The essential point here is that the assignment $\pi_i$ for all $i\in V$ are independent variables in the linear program above.

$\endgroup$

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.