On a Variant of the Minimum Path Cover Problem in Acyclic Digraphs: Computational Complexity Results and Exact Method

Nour ElHouda Tellache, Roberto Baldacci

The Minimum Path Cover (MPC) problem consists of finding a minimum-cardinality set of node-disjoint paths that cover all nodes in a given graph. We explore a variant of the MPC pro…