The 1-fixed-endpoint Path Cover Problem is Polynomial on Interval Graph

Katerina Asdre, Stavros D. Nikolopoulos

We consider a variant of the path cover problem, namely, the $k$-fixed-endpoint path cover problem, or kPC for short, on interval graphs. Given a graph $G$ and a subset $\mathcal{T…