An international team from the University of Verona, Montana State University and University of Helsinki (Doctoral Researcher Manuel Caceres and Associate Professor Alexandru Tomescu) developed a linear-time parameterized algorithm to find a Minimum Path Cover in a Directed Acyclic Graph (DAG). Their solution constitutes a breakthrough in the problem since the parameter utilized corresponds to the size of the optimal solution, which is small in graphs used in Bioinformatics.
This algorithm is part of the research presented at the ACM-SIAM Symposium on Discrete Algorithms (SODA22) and published in the conference proceedings (Manuel Cáceres, Massimo Cairo, Brendan Mumey, Romeo Rizzi, Alexandru I. Tomescu, Sparsifying, Shrinking and Splicing for Minimum Path Cover in Parameterized Linear Time. SODA 2022: 359 - 376).
The new algorithm is based on a classical reduction to Minimum Flow (Simeon C Ntafos, S Louis Hakimi, On path cover problems in digraphs and applications to program testing. IEEE Transactions on Software Engineering, 5:520–529). The authors created an incremental and structural approach that combines three simple techniques (sparsification, shrinking and splicing) to amortize the algorithm's running time to parameterized linear.