Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916468331905024 |
|---|---|
| author | Korhonen, Tuukka |
| author_facet | Korhonen, Tuukka |
| contents | We present $k^{O(k^2)} m$ time algorithms for various problems about decomposing a given undirected graph by edge cuts or vertex separators of size $<k$ into parts that are ``well-connected'' with respect to cuts or separators of size $<k$; here, $m$ is the total number of vertices and edges of the graph. As an application of our results, we obtain for every fixed $k$ a linear-time algorithm for computing the $k$-edge-connected components of a given graph, solving a long-standing open problem. More generally, we obtain a $k^{O(k^2)} m$ time algorithm for computing a $k$-Gomory-Hu tree of a given graph, which is a structure representing pairwise minimum cuts of size $<k$.
Our main technical result, from which the other results follow, is a $k^{O(k^2)} m$ time algorithm for computing a $k$-lean tree decomposition of a given graph. This is a tree decomposition with adhesion size $<k$ that captures the existence of separators of size $<k$ between subsets of its bags. A $k$-lean tree decomposition is also an unbreakable tree decomposition with optimal unbreakability parameters for the adhesion size bound $k$.
As further applications, we obtain $k^{O(k^2)} m$ time algorithms for $k$-vertex connectivity and for element connectivity $k$-Gomory-Hu tree. All of our algorithms are deterministic.
Our techniques are inspired by the tenth paper of the Graph Minors series of Robertson and Seymour and by Bodlaender's parameterized linear-time algorithm for treewidth. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_02658 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More Korhonen, Tuukka Data Structures and Algorithms Combinatorics We present $k^{O(k^2)} m$ time algorithms for various problems about decomposing a given undirected graph by edge cuts or vertex separators of size $<k$ into parts that are ``well-connected'' with respect to cuts or separators of size $<k$; here, $m$ is the total number of vertices and edges of the graph. As an application of our results, we obtain for every fixed $k$ a linear-time algorithm for computing the $k$-edge-connected components of a given graph, solving a long-standing open problem. More generally, we obtain a $k^{O(k^2)} m$ time algorithm for computing a $k$-Gomory-Hu tree of a given graph, which is a structure representing pairwise minimum cuts of size $<k$. Our main technical result, from which the other results follow, is a $k^{O(k^2)} m$ time algorithm for computing a $k$-lean tree decomposition of a given graph. This is a tree decomposition with adhesion size $<k$ that captures the existence of separators of size $<k$ between subsets of its bags. A $k$-lean tree decomposition is also an unbreakable tree decomposition with optimal unbreakability parameters for the adhesion size bound $k$. As further applications, we obtain $k^{O(k^2)} m$ time algorithms for $k$-vertex connectivity and for element connectivity $k$-Gomory-Hu tree. All of our algorithms are deterministic. Our techniques are inspired by the tenth paper of the Graph Minors series of Robertson and Seymour and by Bodlaender's parameterized linear-time algorithm for treewidth. |
| title | Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2411.02658 |