The Maximum Edge-Disjoint Paths Problem in Bidirected Trees
Thomas Erlebach, Klaus Jansen · SIAM Journal on Discrete Mathematics · 2001
A bidirected tree is the directed graph obtained from an undirected tree by replacing each undirected edge by two directed edges with opposite directions. Given a set of directed paths in a bidirected tree, the goal of the maximum edge-disjoint paths problem is to select a maximum-cardinality subset of the paths such that the selected paths are edge-disjoint. This problem can be solved optimally in polynomial time for bidirected trees of constant degree but is APX-hard for bidirected trees of arbitrary degree. For every fixed $\varepsilon >0$, a polynomial-time $(5/3+\varepsilon)$-approximation algorithm is presented.