Bounded indegree $k$-forests problem and a faster algorithm for directed graph augmentation
<|reference_start|>Bounded indegree $k$-forests problem and a faster algorithm for directed graph augmentation: We consider two problems for a directed graph $G$, which we show to be closely related. The first one is to find $k$ edge-disjoint forests in $G$ of maximal size such that the indegree of each vertex in these forests is at most $k$. We describe a min-max characterization for this problem and show that it can be solved in $O(k \delta m \log n)$ time, where $(n,m)$ is the size of $G$ and $\delta$ is the difference between $k$ and the edge connectivity of the graph. The second problem is the directed edge-connectivity augmentation problem, which has been extensively studied before: find a smallest set of directed edges whose addition to the graph makes it strongly $k$-connected. We improve the complexity for this problem from $O(k \delta (m+\delta n)\log n)$ [Gabow, STOC 1994] to $O(k \delta m \log n)$, by exploiting our solution for the first problem. A similar approach with the same complexity also works for the undirected version of the problem.<|reference_end|>
@article{arkhipov2024bounded,
    title={Bounded indegree $k$-forests problem and a faster algorithm for directed
  graph augmentation},
    author={Pavel Arkhipov, Vladimir Kolmogorov},
    journal={arXiv preprint arXiv:2409.14881},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.14881},
    primaryClass={cs.DS cs.DM math.CO}
}