In 1980, Fortune, Hopcroft, and Wyllie showed that the following algorithmic problem (k-EDP) is NP-complete with $k=2$: k Edge-Disjoint Paths (k-EDP) Instance: A digraph $G$, and $k$ pairs $(s_1,t_1),...,(s_k,t_k)$ of vertices of $G$.Question: Do there exist directed paths $P_1,...,P_k$ of $G$, mutually edge-disjoint, such that $P_i$ is from $s_i$ to $t_i$ for $i=1,...,k$?
In this talk we will present a polynomial time algorithm to solve $k$-EDP for fixed $k$ in digraphs with independence number at most $2$. We will also talk about progress made towards solving $k$-EDP in digraphs with independence number at most $\alpha$, for fixed $\alpha$. This is joint work with Paul Seymour.