Maximum Coverage k-Antichains and Chains: A Greedy Approach

Given an input 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$ has been recently solved in almost optimal $|E|^{1+o(1)}$ time [Kogan and Parter, ICALP 2022], the fastest algorithms for MA-$k$ are a recent $(k|E|)^{1+o(1)}$-time solution as well as a $1/2$ approximation running in $|E|^{1+o(1)}$ time [Kogan and Parter, ESA 2024]. In this paper, we simplify and improve previous results. Specifically, we obtain the following:

• An algorithm running in $|E|^{1+o(1)}$ time, beating the $(k|E|)^{1+o(1)}$-time state-of-the-art algorithm, and an algorithm running in parameterized near-linear time $\tilde{O}(\alpha_k |E|)$ time. Our algorithms are simple solutions exploiting a paths-based proof of the Greene-Kleitman theorems leveraged by the $\texttt{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 $\texttt{greedy}$ for antichains and a simple strategy to amortize the cost of computing consecutive maximum antichains. Additionally, we obtain analogous results for MC-$k$ as well as the corresponding dual problems derived from the Greene-Kleitman theorems, which might be of independent interest. We complement these results with two examples (one for chains and one for antichains) showing that, for every $k \ge 2$, $\texttt{greedy}$ misses the tight $1/e$ portion of the optimal coverage for chains, and a $1/4$ portion for antichains. We also show that $\texttt{greedy}$ is a $\Omega(\log{|V|})$ factor away from minimality when required to cover all vertices: previously unknown for sets of chains or antichains.