  In this paper we revisit the classical Edge Disjoint Paths (EDP) problem,
where one is given an undirected graph G and a set of terminal pairs P and asks
whether G contains a set of pairwise edge-disjoint paths connecting every
terminal pair in P. Our focus lies on structural parameterizations for the
problem that allow for efficient (polynomial-time or fpt) algorithms. As our
first result, we answer an open question stated in Fleszar, Mnich, and
Spoerhase (2016), by showing that the problem can be solved in polynomial time
if the input graph has a feedback vertex set of size one. We also show that EDP
parameterized by the treewidth and the maximum degree of the input graph is
fixed-parameter tractable.
  Having developed two novel algorithms for EDP using structural restrictions
on the input graph, we then turn our attention towards the augmented graph,
i.e., the graph obtained from the input graph after adding one edge between
every terminal pair. In constrast to the input graph, where EDP is known to
remain NP-hard even for treewidth two, a result by Zhou et al. (2000) shows
that EDP can be solved in non-uniform polynomial time if the augmented graph
has constant treewidth; we note that the possible improvement of this result to
an fpt-algorithm has remained open since then. We show that this is highly
unlikely by establishing the W[1]-hardness of the problem parameterized by the
treewidth (and even feedback vertex set) of the augmented graph. Finally, we
develop an fpt-algorithm for EDP by exploiting a novel structural parameter of
the augmented graph.
