Maximum Coverage $k$-Antichains and Chains: A Greedy Approach
For researchers in combinatorial optimization and graph algorithms, this work improves the state-of-the-art for a classic problem, though the improvements are incremental.
The authors present faster algorithms for the Maximum Coverage k-Antichains problem, achieving near-linear time and a (1-1/e)-approximation that beats the previous 1/2-approximation. They also show that greedy algorithms can be far from optimal for covering all vertices.
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 $α_k$ (resp. $β_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}(α_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(α_1^2|V| + (α_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 $Ω(\log{|V|})$ factor away from minimality when required to cover all vertices: previously unknown for sets of chains or antichains.