2
$\begingroup$

Given an undirected weighted graph, we seek a pair of node-disjoint path between $2$ nodes $s$ and $t$: if the objective is to minimize the total path cost, the Suurballe algorithm can be applied; now our objective is to minimize $\max\{C(P_1),C(P_2)\}$, where $C(P_i)$ denotes the cost of path $P_i$, this problem is NP-hard (it is polynomially approximatable in DAG), is there any approximation algorithm for general graphs?

If each edge is also associated a delay, how about the above problems under the aditional constraint that the delay of each path is upper-bounded by a parameter $T$, in this case, is the min-sum version NP-hard? and how about approximation algorithm solving the problems?

$\endgroup$

1 Answer 1

1
$\begingroup$

You can solve these problems via integer linear programming as follows. Let $c_{i,j}$ be the cost of edge $(i,j)$. Let binary decision variable $x_{i,j,p}$ indicate whether edge $(i,j)$ appears in path $p\in\{1,2\}$. For the min-sum path cost, the problem is to minimize $\sum_{i,j,p} c_{i,j} x_{i,j,p}$ subject to \begin{align} \sum_j x_{i,j,p} - \sum_j x_{j,i,p} &= \begin{cases} 1 &\text{if $i=s$} \\ -1 &\text{if $i=t$} \\ 0 &\text{if $i\notin \{s,t\}$} \\ \end{cases} &&\text{for $i\in N$ and $p\in\{1,2\}$} \tag1 \\ \sum_{i,j:\ k\in\{i,j\}} \sum_p x_{i,j,p} &\le 1 &&\text{for $k\in N \setminus \{s,t\}$} \tag2\\ \end{align} Constraint $(1)$ enforces an $s$-$t$ path for each $p$. Constraint $(2)$ enforces node-disjointness. For the min-max path cost, the problem is to minimize $z$ subject to $(1)$, $(2)$, and $$\sum_{i,j} c_{i,j} x_{i,j,p} \le z \quad \text{for $p\in\{1,2\}$} \tag3$$ The delay constraint is $$\sum_{i,j} d_{i,j} x_{i,j,p} \le T \quad \text{for $p\in\{1,2\}$} \tag4$$

$\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.