An optimal algorithm for the k-fixed-endpoint path cover on proper
interval graphs

George B. Mertzios, Walter Unger

In this paper we consider the $k$-fixed-endpoint path cover problem
on proper interval graphs, which is a generalization of the path
cover problem. Given a graph $G$ and a set $T$ of $k$ vertices, a
$k$-fixed-endpoint path cover of $G$ with respect to $T$ is a set of
vertex-disjoint simple paths that covers the vertices of $G$, such that
the vertices of $T$ are all endpoints of these paths. The goal is to
compute a $k$-fixed-endpoint path cover of $G$ with minimum cardinality.
We propose an optimal algorithm for this problem with runtime $O(n)$,
where $n$ is the number of intervals in $G$. This algorithm is based
on the \emph{Stair Normal Interval Representation (SNIR) matrix} that
characterizes proper interval graphs. In this characterization, every
maximal clique of the graph is represented by one matrix element; the
proposed algorithm uses this structural property, in order to determine
directly the paths in an optimal solution.