License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2022.72
URN: urn:nbn:de:0030-drops-170101
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17010/
Khan, Shahbaz ;
Tomescu, Alexandru I.
Optimizing Safe Flow Decompositions in DAGs
Abstract
Network flow is one of the most studied combinatorial optimization problems having innumerable applications. Any flow on a directed acyclic graph G having n vertices and m edges can be decomposed into a set of O(m) paths. The applications of such a flow decomposition range from network routing to the assembly of biological sequences. However, in some applications, each solution (decomposition) corresponds to some particular data that generated the original flow. Given the possibility of multiple optimal solutions, no optimization criterion ensures the identification of the correct decomposition. Hence, recently flow decomposition was studied [RECOMB22] in the Safe and Complete framework, particularly for RNA Assembly. The proposed solution reported all the safe paths, i.e., the paths which are subpath of every possible solution of flow decomposition.
They presented a characterization of the safe paths, resulting in an O(mn+out_R) time algorithm to compute all safe paths, where out_R is the size of the raw output reporting each safe path explicitly. They also showed that out_R can be Ω(mn²) in the worst case but O(m) in the best case. Hence, they further presented an algorithm to report a concise representation of the output out_C in O(mn+out_C) time, where out_C can be Ω(mn) in the worst case but O(m) in the best case.
In this work, we study how different safe paths interact, resulting in optimal output-sensitive algorithms requiring O(m+out_R) and O(m+out_C) time for computing the existing representations of the safe paths. Our algorithm uses a novel data structure called Path Tries, which may be of independent interest. Further, we propose a new characterization of the safe paths resulting in the optimal representation of safe paths out_O, which can be Ω(mn) in the worst case but requires optimal O(1) space for every safe path reported. We also present a near-optimal algorithm to compute all the safe paths in O(m+out_Olog n) time. The new representation also establishes tighter worst case bounds Θ(mn²) and Θ(mn) bounds for out_R and out_C (along with out_O), respectively.
Overall we further develop the theory of safe and complete solutions for the flow decomposition problem, giving an optimal algorithm for the explicit representation, and a near-optimal algorithm for the optimal representation of the safe paths.
BibTeX - Entry
@InProceedings{khan_et_al:LIPIcs.ESA.2022.72,
author = {Khan, Shahbaz and Tomescu, Alexandru I.},
title = {{Optimizing Safe Flow Decompositions in DAGs}},
booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)},
pages = {72:1--72:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-247-1},
ISSN = {1868-8969},
year = {2022},
volume = {244},
editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17010},
URN = {urn:nbn:de:0030-drops-170101},
doi = {10.4230/LIPIcs.ESA.2022.72},
annote = {Keywords: safety, flows, networks, directed acyclic graphs}
}
|
Keywords: |
|
safety, flows, networks, directed acyclic graphs |
|
Collection: |
|
30th Annual European Symposium on Algorithms (ESA 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
01.09.2022 |
