Seminars & Colloquia
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.
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
No media files available at this time
Host is responsible for requesting video recording by filling out this Web form. For other technical issues, contact us at firstname.lastname@example.org.
No streaming video available at this time