Faster algorithms for packing forests in graphs and related problems
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912842031038464 |
|---|---|
| author | Arkhipov, Pavel Kolmogorov, Vladimir |
| author_facet | Arkhipov, Pavel Kolmogorov, Vladimir |
| contents | We consider several problems related to packing forests in graphs. The first one is to find $k$ edge-disjoint forests in a directed graph $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 almost linear time for fixed $k$, extending the algorithm of [Gabow, 1995]. Specifically, the complexity is $O(k δm \log n)$, where $n, m$ are the number of vertices and edges in $G$ respectively, and $δ= \max\{1, k - k_G\}$, where $k_G$ is the edge connectivity of the graph. Using our solution to this problem, we improve complexities for two existing applications:
(1) $k$-forest problem: find $k$ forests in an undirected 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.
(2) Directed edge-connectivity augmentation problem: find a smallest set of directed edges whose addition to the given directed graph makes it strongly $k$-connected. We improve the deterministic complexity for this problem from $O(k δ(m+δn)\log n)$ [Gabow, STOC 1994] to $O(k δm \log n)$. 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_20314 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Faster algorithms for packing forests in graphs and related problems Arkhipov, Pavel Kolmogorov, Vladimir Data Structures and Algorithms We consider several problems related to packing forests in graphs. The first one is to find $k$ edge-disjoint forests in a directed graph $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 almost linear time for fixed $k$, extending the algorithm of [Gabow, 1995]. Specifically, the complexity is $O(k δm \log n)$, where $n, m$ are the number of vertices and edges in $G$ respectively, and $δ= \max\{1, k - k_G\}$, where $k_G$ is the edge connectivity of the graph. Using our solution to this problem, we improve complexities for two existing applications: (1) $k$-forest problem: find $k$ forests in an undirected 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. (2) Directed edge-connectivity augmentation problem: find a smallest set of directed edges whose addition to the given directed graph makes it strongly $k$-connected. We improve the deterministic complexity for this problem from $O(k δ(m+δn)\log n)$ [Gabow, STOC 1994] to $O(k δm \log n)$. A similar approach with the same complexity also works for the undirected version of the problem. |
| title | Faster algorithms for packing forests in graphs and related problems |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2409.20314 |