KAIST Discrete Math Seminar

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₁,t₁),(s₂,t₂),…,(s_k,t_k) in G (which are sometimes called terminals). Are there disjoint paths P₁,…,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.