Algorithms for finding disjoint path covers in unit interval graphs

A many-to-many kk-disjoint path cover   (kk-DPC for short) of a graph GG joining the pairwise disjoint vertex sets SS and TT, each of size kk, is a collection of kk vertex-disjoint paths between SS and TT, which altogether cover every vertex of GG. This is classified as paired  , if each vertex of SS must be joined to a specific vertex of TT, or unpaired, if there is no such constraint. In this paper, we develop a linear-time algorithm for the Unpaired DPC problem of finding an unpaired DPC joining SS and TT given in a unit interval graph, to which the One-to-One DPC and the One-to-Many DPC problems are reduced in linear time. Additionally, we show that the Paired   kk-DPC problem on a unit interval graph is polynomially solvable for any fixed kk.