A faster algorithm for the $k$-forest problem: breaking the $O_k(n^3/2)$ complexity barrier
<|reference_start|>A faster algorithm for the $k$-forest problem: breaking the $O_k(n^3/2)$ complexity barrier: The $k$-forest problem asks to find $k$ forests in a graph $G$ maximizing the number of edges in their union. We show how to solve this problem in $O(k^3 \min\{kn, m\} \log^2 n + k \cdot{\rm MAXFLOW}(m, m) \log n)$ time, breaking the $O_k(n^{3/2})$ complexity barrier of previously known approaches. Our algorithm relies on three subroutines: the directed $k$-forest problem with bounded indegree condition, the $k$-pseudoforest problem, and the top clump computation.<|reference_end|>
@article{arkhipov2024a,
    title={A faster algorithm for the $k$-forest problem: breaking the
  $O_k(n^{3/2})$ complexity barrier},
    author={Pavel Arkhipov, Vladimir Kolmogorov},
    journal={arXiv preprint arXiv:2409.20314},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.20314},
    primaryClass={cs.DS}
}