  We study the classical NP-hard problems of finding maximum-size subsets from
given sets of $k$ terminal pairs that can be routed via edge-disjoint paths
(MaxEDP) or node-disjoint paths (MaxNDP) in a given graph. The approximability
of MaxEDP/NDP is currently not well understood; the best known lower bound is
$\Omega(\log^{1/2-\epsilon}{n})$, assuming
NP$~\not\subseteq~$ZPTIME$(n^{\mathrm{poly}\log n})$. This constitutes a
significant gap to the best known approximation upper bound of $O(\sqrt{n})$
due to Chekuri et al. (2006) and closing this gap is currently one of the big
open problems in approximation algorithms. In their seminal paper, Raghavan and
Thompson (Combinatorica, 1987) introduce the technique of randomized rounding
for LPs; their technique gives an $O(1)$-approximation when edges (or nodes)
may be used by $O(\frac{\log n}{\log\log n})$ paths.
  In this paper, we strengthen the above fundamental results. We provide new
bounds formulated in terms of the feedback vertex set number $r$ of a graph,
which measures its vertex deletion distance to a forest. In particular, we
obtain the following.
  * For MaxEDP, we give an $O(\sqrt{r}\cdot \log^{1.5}{kr})$-approximation
algorithm. As $r\leq n$, up to logarithmic factors, our result strengthens the
best known ratio $O(\sqrt{n})$ due to Chekuri et al.
  * Further, we show how to route $\Omega(\mathrm{OPT})$ pairs with congestion
$O(\frac{\log{kr}}{\log\log{kr}})$, strengthening the bound obtained by the
classic approach of Raghavan and Thompson.
  * For MaxNDP, we give an algorithm that gives the optimal answer in time
$(k+r)^{O(r)}\cdot n$. If $r$ is at most triple-exponential in $k$, this
improves the best known algorithm for MaxNDP with parameter $k$, by
Kawarabayashi and Wollan (STOC 2010).
  We complement these positive results by proving that MaxEDP is NP-hard even
for $r=1$, and MaxNDP is W$[1]$-hard for parameter $r$.
