Solving Minimum Path Cover on a DAG

We discuss an algorithm to find a minimum path cover on a DAG.

Introduction

In this story, we will first define the minimum path cover problem (MPC) on graphs and then model a fictitious scenario as MPC. In turn, we will analyze the structure of our model and reduce MPC to the maximum matching problem for certain special cases. We will conclude the story with the solution.

MPC of a graph is a set of vertex-disjoint paths with minimum cardinality such that the union of…