Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.06459 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912226371174400 |
|---|---|
| author | Cáceres, Manuel Grigorjew, Andreas Jiamjitrak, Wanchote Po Tomescu, Alexandru I. |
| author_facet | Cáceres, Manuel Grigorjew, Andreas Jiamjitrak, Wanchote Po Tomescu, Alexandru I. |
| contents | 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}(α_k|E|)$ time, where $α_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(α_1^2|V| + (α_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 $Ω(\log{|V|})$ factor away from minimality when required to cover all vertices: previously unknown for sets of chains or antichains. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_06459 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Maximum Coverage $k$-Antichains and Chains: A Greedy Approach Cáceres, Manuel Grigorjew, Andreas Jiamjitrak, Wanchote Po Tomescu, Alexandru I. Data Structures and Algorithms 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}(α_k|E|)$ time, where $α_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(α_1^2|V| + (α_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 $Ω(\log{|V|})$ factor away from minimality when required to cover all vertices: previously unknown for sets of chains or antichains. |
| title | Maximum Coverage $k$-Antichains and Chains: A Greedy Approach |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.06459 |