**FYI (Department Colloquium)**

National Institute of Informatics, Tokyo, Japan.

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 (s

_{1},t_{1}),(s_{2},t_{2}),…,(s_{k},t_{k}) in G (which are sometimes calledterminals). Are there disjoint paths P_{1},…,P_{k}in G such that P_{i}joins s_{i}and t_{i}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.

Tags: colloquium, KenichiKawarabayashi