## 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**

**Abstract:**

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