Practical Minimum Path Cover
Loading...
Access rights
openAccess
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2024-07
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
19
Series
Leibniz International Proceedings in Informatics, LIPIcs ; Volume 301
Abstract
Computing a minimum path cover (MPC) of a directed acyclic graph (DAG) is a fundamental problem with a myriad of applications, including reachability. Although it is known how to solve the problem by a simple reduction to minimum flow, recent theoretical advances exploit this idea to obtain algorithms parameterized by the number of paths of an MPC, known as the width. These results obtain fast [Mäkinen et al., TALG 2019] and even linear time [Cáceres et al., SODA 2022] algorithms in the small-width regime. In this paper, we present the first publicly available high-performance implementation of state-of-the-art MPC algorithms, including the parameterized approaches. Our experiments on random DAGs show that parameterized algorithms are orders-of-magnitude faster on dense graphs. Additionally, we present new fast pre-processing heuristics based on transitive edge sparsification. We show that our heuristics improve MPC-solvers by orders of magnitude.Description
Publisher Copyright: © Manuel Cáceres.
Keywords
algorithm engineering, directed acyclic graph, edge sparsification, maximum flow, minimum path cover, parameterized algorithms
Other note
Citation
Cáceres, M, Mumey, B, Toivonen, S & Tomescu, A I 2024, Practical Minimum Path Cover . in L Liberti (ed.), 22nd International Symposium on Experimental Algorithms, SEA 2024 ., 3, Leibniz International Proceedings in Informatics, LIPIcs, vol. 301, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-19, International Symposium on Experimental Algorithms, Vienna, Austria, 23/07/2024 . https://doi.org/10.4230/LIPIcs.SEA.2024.3