2026-09-22T12:32:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27244 2026-09-05T20:16:28Z ddc:004 open_access

Maximum Coverage k-Antichains and Chains: A Greedy Approach Cáceres, Manuel Grigorjew, Andreas Jiamjitrak, Wanchote Po Tomescu, Alexandru I. Maximum coverage antichains maximum coverage chains directed acyclic graph minimum cost flow greedy set cover parameterized algorithms approximation algorithms 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 simplify and improve previous results. Specifically, we obtain the following for MA-k: - An algorithm running in |E|^{1+o(1)} time, and an algorithm running in parameterized near-linear Õ(α_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(α₁²|V| + (α₁+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. 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 ≥ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Manuel Cáceres and Andreas Grigorjew and Wanchote Po Jiamjitrak and Alexandru I. Tomescu 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.108 urn:nbn:de:0030-drops-272442 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.108 eng https://creativecommons.org/licenses/by/4.0/legalcode