Sparsifying, Shrinking and Splicing for Minimum Path Cover in Parameterized Linear Time

Manuel Cáceres, Massimo Cairo, Brendan Mumey +2

A minimum path cover (MPC) of a directed acyclic graph (DAG) $G=(V,E)$ is a minimum-size set of paths that together cover all the vertices of the DAG. Computing an MPC is a basic…