MINIMUM MAXIMUM DISJOINT CONNECTING PATHS

• INSTANCE: Graph $G=\left(V,E\right)$, length function $l:E \rightarrow N$, and a pair of vertices s,t in V.

• SOLUTION: Two vertex disjoint paths in G connecting s and t, i.e. two sequences of vertices $u_1,u_2,\ldots,u_m$ and $v_1,v_2,\ldots,v_n$ such that $\vert\{u_1,u_2,\ldots,u_m,v_1,v_2,\ldots,v_n\}\vert=m+n$, $(s,u_1)$, $(s,v_1)$, $(u_m,t)$, and $(v_n,t)$ are included in E, and for any i, $(u_i ,u_{i+1})$ and $(v_i ,v_{i+1})$ are included in E.

• MEASURE: The longest of the two paths, i.e. $\max(l(s,u_1)+\sum_{i=1}^{m-1} l(u_i,u_{i+1})+l(u_m,t), l(s,v_1)+\sum_{i=1}^{n-1} l(v_i,v_{i+1})+l(v_n,t))$.

  
  

• Good News: Approximable within 2 [354].

• Comment: Approximable within 2 also if the paths should be edge disjoint instead of vertex disjoint. Variation in which the graph is directed and we look for two vertex (edge) disjoint directed paths is also approximable within 2, and is not approximable within $2-\varepsilon$ for any $\varepsilon >0$ [354].

• Garey and Johnson: Similar to ND41