Minimum Path Cover in a parameterized linear time accepted at SODA 2022

Finding a Minimum Path Cover of a DAG is a fundamental algorithmic problem, with applications in various fields, including Bioinformatics. While a classical solution leads to a quadratic-time algorithm, many applications process massive graphs requiring a better running time. The Graph Algorithms Team developed a linear-time parameterized solution to tackle this issue. This work constitutes a breakthrough for the problem, and it was recently presented at SODA 2022.

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.