MAXIMUM DISJOINT CONNECTING PATHS

• INSTANCE: Multigraph $G=\left(V,E\right)$, collection of vertex pairs $T=\{(s_1,t_1),(s_2,t_2),\ldots,(s_k,t_k)\}$.

• SOLUTION: A collection of edge disjoint paths in G connecting some of the pairs $(s_i,t_i)$, i.e. sequences of vertices $u_1,u_2,\ldots,u_m$ such that, for some i, $u_1=s_i$, $u_m=t_i$, and for any j, $(u_j ,u_{j+1})\in E$.

• MEASURE: The number of vertex pairs $(s_i,t_i)$ that are connected by the paths.

  
  

• Good News: Approximable within $\min\{\sqrt{\vert E\vert},\vert E\vert/\mbox{\sl opt}\}$ [447].

• Bad News: Not approximable within $O(2^{\log^{1-\varepsilon }\vert V\vert}$ for any $\varepsilon >0$ unless NP$\subset$QP [366].

• Comment: Similar to MINIMUM UNSPLITTABLE FLOW. Approximable within $O(\mbox{polylog}\vert V\vert)$ for constant degree graphs and butterfly graphs [447]. Approximable within 2 if G is a tree with parallel edges. Approximable within $O(\log \vert V\vert)$ if G is a two-dimensional mesh [43], or more generally, if G is a nearly-Eulerian uniformly high-diameter planar graph [324].

  Variation in which the objective is to minimize the number of rounds that together connect all pairs, is approximable within $O(\sqrt{\vert E\vert}\log\vert V\vert)$ on general multigraphs and within $O(\mbox{polylog}\vert V\vert)$ on butterfly graphs [447].

  MINIMUM PATH COLORING is the variation in which each path is assigned a color, where only paths with the same color need to be edge disjoint, and where the objective is to minimize the number of colors that are needed to connect all vertex pairs in the input. This problem is approximable within 3/2 on trees, within 2 on cycles [415], within $O(\mbox{polylog}\log \vert V\vert)$ on two-dimensional meshes [412], and within $O(\log \vert V\vert)$ on nearly-Eulerian uniformly high-diameter planar graphs [324].

• Garey and Johnson: Similar to ND40