Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2021
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910415862104064 |
|---|---|
| author | Chalermsook, Parinya Kaul, Matthias Mnich, Matthias Spoerhase, Joachim Uniyal, Sumedha Vaz, Daniel |
| author_facet | Chalermsook, Parinya Kaul, Matthias Mnich, Matthias Spoerhase, Joachim Uniyal, Sumedha Vaz, Daniel |
| contents | The fundamental sparsest cut problem takes as input a graph $G$ together with the edge costs and demands, and seeks a cut that minimizes the ratio between the costs and demands across the cuts. For $n$-node graphs~$G$ of treewidth~$k$, \chlamtac, Krauthgamer, and Raghavendra (APPROX 2010) presented an algorithm that yields a factor-$2^{2^k}$ approximation in time $2^{O(k)} \cdot \operatorname{poly}(n)$. Later, Gupta, Talwar and Witmer (STOC 2013) showed how to obtain a $2$-approximation algorithm with a blown-up run time of $n^{O(k)}$. An intriguing open question is whether one can simultaneously achieve the best out of the aforementioned results, that is, a factor-$2$ approximation in time $2^{O(k)} \cdot \operatorname{poly}(n)$.
In this paper, we make significant progress towards this goal, via the following results:
(i) A factor-$O(k^2)$ approximation that runs in time $2^{O(k)} \cdot \operatorname{poly}(n)$, directly improving the work of Chlamtáč et al. while keeping the run time single-exponential in $k$.
(ii) For any $\varepsilon>0$, a factor-$O(1/\varepsilon^2)$ approximation whose run time is $2^{O(k^{1+\varepsilon}/\varepsilon)} \cdot \operatorname{poly}(n)$, implying a constant-factor approximation whose run time is nearly single-exponential in $k$ and a factor-$O(\log^2 k)$ approximation in time $k^{O(k)} \cdot \operatorname{poly}(n)$.
Key to these results is a new measure of a tree decomposition that we call combinatorial diameter, which may be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2111_06299 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter Chalermsook, Parinya Kaul, Matthias Mnich, Matthias Spoerhase, Joachim Uniyal, Sumedha Vaz, Daniel Data Structures and Algorithms The fundamental sparsest cut problem takes as input a graph $G$ together with the edge costs and demands, and seeks a cut that minimizes the ratio between the costs and demands across the cuts. For $n$-node graphs~$G$ of treewidth~$k$, \chlamtac, Krauthgamer, and Raghavendra (APPROX 2010) presented an algorithm that yields a factor-$2^{2^k}$ approximation in time $2^{O(k)} \cdot \operatorname{poly}(n)$. Later, Gupta, Talwar and Witmer (STOC 2013) showed how to obtain a $2$-approximation algorithm with a blown-up run time of $n^{O(k)}$. An intriguing open question is whether one can simultaneously achieve the best out of the aforementioned results, that is, a factor-$2$ approximation in time $2^{O(k)} \cdot \operatorname{poly}(n)$. In this paper, we make significant progress towards this goal, via the following results: (i) A factor-$O(k^2)$ approximation that runs in time $2^{O(k)} \cdot \operatorname{poly}(n)$, directly improving the work of Chlamtáč et al. while keeping the run time single-exponential in $k$. (ii) For any $\varepsilon>0$, a factor-$O(1/\varepsilon^2)$ approximation whose run time is $2^{O(k^{1+\varepsilon}/\varepsilon)} \cdot \operatorname{poly}(n)$, implying a constant-factor approximation whose run time is nearly single-exponential in $k$ and a factor-$O(\log^2 k)$ approximation in time $k^{O(k)} \cdot \operatorname{poly}(n)$. Key to these results is a new measure of a tree decomposition that we call combinatorial diameter, which may be of independent interest. |
| title | Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2111.06299 |