The k edge-disjoint paths problem in digraphs with bounded independence number
The k edge-disjoint paths problem in digraphs with bounded independence number
-
Alexandra Ovetsky Fradkin, Princeton University
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 (s1,t1),...,(sk,tk) of vertices of G.Question: Do there exist directed paths P1,...,Pk of G, mutually edge-disjoint, such that Pi is from si to ti 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 α, for fixed α. This is joint work with Paul Seymour.