Seminars & Colloquia

Irene Muzi

University of Rome

"The 1/p-IntegralLinkage Problem in Directed Acyclic Graphs"

Wednesday April 13, 2016 03:00 PM
Location: 3211, EBII NCSU Centennial Campus
(Visitor parking instructions)

This talk is part of the Theory Seminar Series



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.

Short Bio:

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.

Host: Blair D. Sullivan, CSC

Media Files:
No media files available at this time

Video Presentation: Host is responsible for requesting video recording by filling out this Web form. For other technical issues, contact us at
No streaming video available at this time

Back to Seminar Listings
Back to Colloquia Home Page