Maximum Coverage k-Antichains and Chains: A Greedy Approach
We obtain fast algorithms for maximum coverage $k$-antichains and chains, and show the limits of the $\texttt{greedy}$ heuristic in these contexts.
Feb 7, 2025
Minimum Path Cover in Parameterized Linear Time
We obtain a new MPC parameterized algorithm for DAGs running in time $O(k^2|V| + |E|)$. Our algorithm is the first solving the problem in parameterized linear time. Additionally, we obtain an edge sparsification algorithm preserving the width of a DAG but reducing $|E|$ to less than $2|V|$. This algorithm runs in time $O(k^2|V|)$ and requires an MPC of a DAG as input, thus its total running time is the same as the running time of our MPC algorithm.
Nov 17, 2022