## (Colloquium) Ken-ichi Kawarabayashi, The disjoint paths problem: Algorithm and Structure

FYI (Department Colloquium)
The disjoint paths problem: Algorithm and Structure
Ken-ichi Kawarabayashi (河原林 健一)
National Institute of Informatics, Tokyo, Japan.
2009/11/26 Thursday 4:30PM-5:30PM (Room 1501)

In this talk, we shall discuss the following well-known problem, which
is called the disjoint paths problem.

Given a graph G with n vertices and m edges, k pairs of vertices (s1,t1),(s2,t2),…,(sk,tk) in G (which are sometimes called terminals). Are there disjoint paths P1,…,Pk in G such that Pi joins si and ti for i=1,2,…,k?

We discuss recent progress on this topic, including algorithmic aspect of the disjoint paths problem.

We also discuss some structure theorems without the k disjoint paths. Topics include the uniquely linkage problem and the connectivity function that guarantees the existence of the k disjoint paths.