2026-07-22T06:26:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18083 2024-03-06T11:00:58Z ddc:004 open_access

Minimum Chain Cover in Almost Linear Time Cáceres, Manuel Minimum chain cover directed acyclic graph minimum flow flow decomposition mergeable dictionaries amortized running time A minimum chain cover (MCC) of a k-width directed acyclic graph (DAG) G = (V, E) is a set of k chains (paths in the transitive closure) of G such that every vertex appears in at least one chain in the cover. The state-of-the-art solutions for MCC run in time Õ(k(|V|+|E|)) [Mäkinen et at., TALG], O(T_{MF}(|E|) + k|V|), O(k²|V| + |E|) [Cáceres et al., SODA 2022], Õ(|V|^{3/2} + |E|) [Kogan and Parter, ICALP 2022] and Õ(T_{MCF}(|E|) + √k|V|) [Kogan and Parter, SODA 2023], where T_{MF}(|E|) and T_{MCF}(|E|) are the running times for solving maximum flow (MF) and minimum-cost flow (MCF), respectively. In this work we present an algorithm running in time O(T_{MF}(|E|) + (|V|+|E|)log k). By considering the recent result for solving MF [Chen et al., FOCS 2022] our algorithm is the first running in almost linear time. Moreover, our techniques are deterministic and derive a deterministic near-linear time algorithm for MCC if the same is provided for MF. At the core of our solution we use a modified version of the mergeable dictionaries [Farach and Thorup, Algorithmica], [Iacono and Özkan, ICALP 2010] data structure boosted with the SIZE-SPLIT operation and answering queries in amortized logarithmic time, which can be of independent interest. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Manuel Cáceres 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.31 urn:nbn:de:0030-drops-180834 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.31 eng https://creativecommons.org/licenses/by/4.0/legalcode