A sufficient condition for the unpaired k-disjoint path coverability of interval graphs

Given disjoint source and sink sets, $$S = \{ s_1,\ldots ,s_k\}$$ and $$T = \{t_1,\ldots , t_k\}$$ , in a graph G, an unpaired k-disjoint path cover joining S and T is a set of pairwise vertex-disjoint paths $$\{ P_1, \ldots , P_k\}$$ that altogether cover every vertex of the graph, in which $$P_i$$ is a path from source $$s_i$$ to some sink $$t_j$$ . In this paper, we prove that if the scattering number, $${{\,\mathrm{sc}\,}}(G)$$ , of an interval graph G of order $$n \ge 2k$$ is less than or equal to $$-k$$ , there exists an unpaired k-disjoint path cover joining S and T in G for any possible configurations of source and sink sets S and T of size k each. The bound $${{\,\mathrm{sc}\,}}(G) \le -k$$ is tight; moreover, the proof directly leads to a quadratic algorithm for building an unpaired k-disjoint path cover.