The k edgedisjoint paths problem in digraphs with bounded independence number
The k edgedisjoint paths problem in digraphs with bounded independence number

Alexandra Ovetsky Fradkin, Princeton University
Fine Hall 224
In 1980, Fortune, Hopcroft, and Wyllie showed that the following algorithmic problem (kEDP) is NPcomplete with $k=2$: k EdgeDisjoint Paths (kEDP) 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 edgedisjoint, 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.