2025/02/10 by Manuel Cáceres, Andreas Grigorjew, Cáceres, Manuel +5 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2502.06459
openalex publication_date 2025/02/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
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 obtain the following for MA-k: - An algorithm running in |E|1+o(1) time, and an algorithm running in parameterized near-linear O(α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(α12|V| + (α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 ≥ 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.