Maximum Coverage k-Antichains and Chains: A Greedy Approach
$\alpha_k$ and $\beta_k$ networks
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 of vertices covered by these antichains (resp. chains). While MC-$k$ has been recently solved in (almost) optimal $O(|E|^{1+o(1)})$ time [Kogan and Parter, ICALP 2022], the fastest known algorithm for MA-$k$ is a recent $(k|E|)^{1+o(1)}$-time solution [Kogan and Parter, ESA 2024] as well as a $1/2$ approximation running in $|E|^{1+o(1)}$ time in the same paper. In this paper, we leverage a paths-based proof of the Greene-Kleitmann (GK) theorem with the help of the greedy algorithm for set cover and recent advances on fast algorithms for flows and shortest paths to obtain the following results for MA-$k$:
- The first (exact) algorithm running in $|E|^{1+o(1)}$ time, hence independent in $k$.
- A randomized algorithm running in $\tilde{O}(\alpha_k |E|)$ time, where $\alpha_k$ is the size of the optimal solution. That is, a near-linear parameterized running time, generalizing the result of [Mäkinen et al., ACM TALG] obtained for $k=1$.
- An approximation algorithm running in time $O(\alpha_1^2|V| + (\alpha_1+k)|E|)$ with approximation ratio of $(1-1/e) > 0.63 > 1/2$.
Our last two solutions rely on the use of greedy set cover, first exploited in [Felsner et al., Order 2003] for chains, which we now apply to antichains. We complement these results with two examples (one for chains and one for antichains) showing that, for every $k \ge 2$, greedy misses a $1/4$ portion of the optimal coverage. 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. Finally, some of our intermediate results show efficient solutions to related problems, which can be of independent interest.
