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

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 polynomial problem, dating back to Dilworth's and Fulkerson's results in the 1950s. Since the size k of an MPC (also known as the width) can be small in practical applications, research has also studied algorithms whose running time is parameterized on k. We obtain two new MPC parameterized algorithms for DAGs running in time O(k2|V| log |V| + |E|) and O(k3|V| + |E|). We also obtain a parallel algorithm running in O(k2|V| + |E|) parallel steps and using O(log |V|) processors (in the PRAM model). Our latter two algorithms are the first solving the problem in parameterized linear time. Finally, we show that we can transform (in O(k2|V|) time) a given MPC into another MPC that uses less than 2|V| distinct edges, which we prove to be asymptotically tight. As such, we also obtain edge sparsification algorithms preserving the width of the DAG with the same running time as our MPC algorithms. At the core of all our algorithms we interleave the usage of three techniques: transitive sparsification, shrinking of a path cover, and the splicing of a set of paths along a given path.