Min-sum and min-max node-disjoint path problems

Question

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?

Answer 1

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