Maximum Coverage $k$-Antichains and Chains: A Greedy Approach

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 $\hat{I}{\pm }_k$ (resp. ${\hat{I}}_k^2$) 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}(\hat{I}{\pm }_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(\hat{I}{\pm }_1^2|V|+(\hat{I}{\pm }_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 $\hat{I}\text{c◯}(\log |V|)$ factor away from minimality when required to cover all vertices: previously unknown for sets of chains or antichains.