# Minimum Chain Cover in Almost Linear Time

Preprint · Manuel Caceres

- Archive id: arxiv:2305.02166
- Published: 2023-05-03
- arXiv: https://arxiv.org/abs/2305.02166
- Source URL: https://arxiv.org/abs/2305.02166
- PDF: https://arxiv.org/pdf/2305.02166
- Provenance: arxiv

## Abstract

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 $\\tilde{O}(k(\|V\|+\|E\|))$ \[Mäkinen et at., TALG\], $O(T\_{MF}(\|E\|) + k\|V\|)$, $O(k^2\|V\| + \|E\|)$ \[Cáceres et al., SODA 2022\], $\\tilde{O}(\|V\|^{3/2} + \|E\|)$ \[Kogan and Parter, ICALP 2022\] and $\\tilde{O}(T\_{MCF}(\|E\|) + \\sqrt{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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.