2026-07-20T14:45:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24523 2025-12-16T14:00:19Z ddc:004 open_access

Safe Sequences via Dominators in DAGs for Path-Covering Problems Sena, Francisco Rizzi, Romeo Tomescu, Alexandru I. directed acyclic graph path cover dominator tree integer linear programming least squares minimum path error A path-covering problem on a directed acyclic graph (DAG) requires finding a set of source-to-sink paths that cover all the nodes, all the arcs, or subsets thereof, and additionally they are optimal with respect to some function. In this paper we study safe sequences of nodes or arcs, namely sequences that appear in some path of every path cover of a DAG. We show that safe sequences admit a simple characterization via cutnodes. Moreover, we establish a connection between maximal safe sequences and leaf-to-root paths in the source- and sink-dominator trees of the DAG, which may be of independent interest in the extensive literature on dominators. With dominator trees, safe sequences admit an O(n)-size representation and a linear-time output-sensitive enumeration algorithm running in time O(m + o), where n and m are the number of nodes and arcs, respectively, and o is the total length of the maximal safe sequences. We then apply maximal safe sequences to simplify Integer Linear Programs (ILPs) for two path-covering problems, LeastSquares and MinPathError, which are at the core of RNA transcript assembly problems from bioinformatics. On various datasets, maximal safe sequences can be computed in under 0.1 seconds per graph, on average, and ILP solvers whose search space is reduced in this manner exhibit significant speed-ups. For example on graphs with a large width, average speed-ups are in the range 50-250× for MinPathError and in the range 80-350× for LeastSquares. Optimizing ILPs using safe sequences can thus become a fast building block of practical RNA transcript assembly tools, and more generally, of path-covering problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Francisco Sena and Romeo Rizzi and Alexandru I. Tomescu 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.55 urn:nbn:de:0030-drops-245230 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.55 eng https://creativecommons.org/licenses/by/4.0/legalcode