2023/05/03 by Caceres, Manuel · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2305.02166
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 O(k(|V|+|E|)) [Mäkinen et at., TALG], O(TMF(|E|) + k|V|), O(k2|V| + |E|) [Cáceres et al., SODA 2022], O(|V|3/2 + |E|) [Kogan and Parter, ICALP 2022] and O(TMCF(|E|) + √(k)|V|) [Kogan and Parter, SODA 2023], where TMF(|E|) and TMCF(|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(TMF(|E|) + (|V|+|E|)logk). 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.