Algorithms for finding disjoint path covers in unit interval graphs

A many-to-many k-disjoint path cover (k-DPC for short) of a graph G joining the pairwise disjoint vertex sets S and T, each of size k, is a collection of k vertex-disjoint paths between S and T, which altogether cover every vertex of G. This is classified as paired, if each vertex of S must be joined to a specific vertex of T, 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 S and T 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 k-DPC problem on a unit interval graph is polynomially solvable for any fixed k. (C) 2016 Elsevier B.V. All rights reserved.