Bounded indegree $k$-forests problem and a faster algorithm for directed graph augmentation
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915555917692928 |
|---|---|
| author | Arkhipov, Pavel Kolmogorov, Vladimir |
| author_facet | Arkhipov, Pavel Kolmogorov, Vladimir |
| contents | 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 δm \log n)$ time, where $(n,m)$ is the size of $G$ and $δ$ 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 δ(m+δn)\log n)$ [Gabow, STOC 1994] to $O(k δ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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_14881 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Bounded indegree $k$-forests problem and a faster algorithm for directed graph augmentation Arkhipov, Pavel Kolmogorov, Vladimir Data Structures and Algorithms Discrete Mathematics Combinatorics 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 δm \log n)$ time, where $(n,m)$ is the size of $G$ and $δ$ 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 δ(m+δn)\log n)$ [Gabow, STOC 1994] to $O(k δ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. |
| title | Bounded indegree $k$-forests problem and a faster algorithm for directed graph augmentation |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2409.14881 |