Given a graph G and distinct ordered pairs of vertices (s_1,t_1),...,(s_k,t_k), the k-VertexDisjointPaths (k-VDP) problem asks for pairwise vertex disjoint paths P_1,...,P_k such that P_i is a path from s_i to t_i. k-VDP is a classical problem in graph theory both in its undirected and directed version. For undirected graphs, Robertson and Seymour showed that k-VDP is solvable in polynomial time when k is fixed. The directed case is considerably harder and it was shown to be NP-hard even when k equals 2 (a result of Fortune, Hopcroft and Wyllie). In this talk we will focus on the 1/p-IntegralLinkage problem, a relaxation of k-VDP that allows for a vertex of G to belong to at most p of the k paths and we will show that a fixed parameter time algorithm exists on directed acyclic graphs when p equals k-1. This is joint work with K. Edwards and P. Wollan.

Irene Muzi is a Ph.D. candidate studying with Paul Wollan in the Dipartmento Informatica at the University of Rome, La Sapienza. She works on the ERC Project DASTCO: Developing and Applying Structural Tools for Combinatorial Objects.