Abstract:Given an acyclic digraph $G = (V,E)$ and a positive integer $k$, the problem of Maximum Coverage $k$-Antichains (resp. Chains) denoted as MA-$k$ (resp. MC-$k$) asks to find $k$ sets of pairwise unreachable vertices, known as antichains (resp. $k$ subsequences of paths, known as chains), maximizing the number $\alpha_k$ (resp. $\beta_k$) of vertices covered by these antichains (resp. chains). While MC-$k$ was solved in almost optimal $|E|^{1+o(1)}$ time~[Kogan and Parter, ICALP'22], the fastest algorithms for MA-$k$ are a $(k|E|)^{1+o(1)}$-time solution and a $|E|^{1+o(1)}$-time $1/2$ approximation~[Kogan and Parter, ESA'24]. We obtain the following for MA-$k$:
- An algorithm running in $|E|^{1+o(1)}$ time, and an algorithm running in parameterized near-linear $\tilde{O}(\alpha_k
|E|)$ time. Our algorithms are simple solutions exploiting a paths-based proof of the Greene-Kleitman theorems leveraged by the greedy algorithm for set cover as well as recent advances in fast algorithms for flows and shortest paths.
- An approximation algorithm running in parameterized linear time $O(\alpha_1^2|V| + (\alpha_1+k)|E|)$ with approximation ratio of $(1-1/e) > 0.63 > 1/2$, beating the state-of-the-art $1/2$ approximation. Our solution uses greedy for antichains and a simple strategy to amortize the cost of computing consecutive maximum antichains.
We complement these results with two examples (one for chains and one for antichains) showing that, for every $k \ge 2$, greedy misses the tight $1/e$ portion of the optimal coverage for chains, and a $1/4$ portion for antichains. We also show that greedy is a $\Omega(\log{|V|})$ factor away from minimality when required to cover all vertices: previously unknown for sets of chains or antichains.
From: Manuel Cáceres [view email]
[v1]
Mon, 10 Feb 2025 13:41:11 UTC (29 KB)
[v2]
Tue, 7 Jul 2026 15:52:31 UTC (104 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。