2022/08/31 by Fernando H. C. Dias, Lucia Williams, Dias, Fernando H. C. +5 · 1 citation
Biochemistry, Genetics and Molecular Biology · #Advanced biosensing and bioanalysis techniques #Combinatorics (math.CO) #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Biological sciences #FOS: Computer and information sciences #FOS: Mathematics #Genomics (q-bio.GN) #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2209.00042
openalex publication_date 2022/08/31 · openalex created_date 2022/09/03 · openalex updated_date 2026/07/28
Minimum flow decomposition (MFD) -- the problem of finding a minimum set of weighted source-to-sink paths that perfectly decomposes a flow -- is a classical problem in Computer Science, and variants of it are powerful models in different fields such as Bioinformatics and Transportation. Even on acyclic graphs, the problem is NP-hard, and most practical solutions have been via heuristics or approximations. While there is an extensive body of research on acyclic graphs, currently, there is no exact solution on graphs with cycles. In this paper, we present the first ILP formulation for three natural variants of the MFD problem in graphs with cycles, asking for a decomposition consisting only of weighted source-to-sink paths or cycles, trails, and walks, respectively. On three datasets of increasing levels of complexity from both Bioinformatics and Transportation, our approaches solve any instance in under 10 minutes. Our implementations are freely available at github.com/algbio/MFD-ILP.