ND44 M AXIMUM D ISJOINT C ONNECTING P ATHS

     
• I NSTANCE : Graph , collection of vertex pairs .
• S OLUTION : A collection of edge disjoint paths in G connecting some of the pairs , i.e. sequences of vertices such that, for some i , , , and for any j , .
• M EASURE : The number of vertex pairs that are connected by the paths.

• Comment: Approximable within 2 if G is a tree with parallel edges. Approximable within if G is a two-dimensional mesh [ 25 ], or more generally, if G is a nearly-Eulerian uniformly high-diameter planar graph [ 234 ].    

  M INIMUM P ATH C OLORING 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 [ 305 ], within on two-dimensional meshes [ 303 ], and within on nearly-Eulerian uniformly high-diameter planar graphs [ 234 ].    

• Garey and Johnson: Similar to ND40