This seminar will use a broad interpretation of "CS theory," and will include talks on related topics in areas such as graph theory.

Unless otherwise noted, talks will be in

Centennial Campus, NCSU

Now in its third year, we officially have a preferred day and time (Monday, 11:00 am) for the seminar, and plan to have approximately one talk per month. Please double-check the schedule, though, as out-of-town speakers may necessitate a change in day. please sign up for our mailing list (directions at the bottom of this page) to receive notification of all talks, times, and locations.

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.

**October 5, 2015**, 11:00 am:** Dana Randall**, Georgia Institute of Technology. * Phase Transitions in Random Structures and Sampling Algorithms.*

**November 2, 2015** 11:00 am:** Jeremy Kun**, University of Illinois, Chicago. * Resilience and new approaches to approximate graph coloring. *

**November 23, 2015**, 11:00 am:** Claire Monteleoni**, George Washington University. * Climate Informatics: Algorithms, Advances, and Open Problems. *

**January 11, 2016** 11:00 am:** Liz Munch**, University at Albany, SUNY. * The Reeb graph interleaving distance *

**February 22, 2016** 11:00 am:** Aaron Clauset**, University of Colorado, Boulder. * Gender, Productivity, and Prestige in Computer Science Faculty Hiring Networks *

**March 28, 2016** 11:00 am:** David Gleich**, Purdue University. * Sparsity and localization in evaluating functions of matrices on modern information networks. *

**April 13, 2016** 3:00 pm:** Irene Muzi**, Sapienza University of Rome. * TBA. *

*postponed to Fall 2016 *:** Cris Moore**, Santa Fe Institute. * TBA. *

To subscribe to the theory seminar announcement mailing list, send an email message to the NCSU list server at mj2@lists.ncsu.edu with "SUBSCRIBE cstheoryseminar" in the body of the message (not the subject line).