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

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?

## 1 Answer

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