Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
No Thumbnail Available
Access rights
openAccess
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2024-01-22
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
ACM Transactions on Algorithms, Volume 20, issue 1, pp. 1-20
Abstract
The fundamental Sparsest Cut problem takes as input a graph G together with edge capacities and demands and seeks a cut that minimizes the ratio between the capacities and demands across the cuts. For n-vertex graphs G of treewidth k, Chlamtáč, Krauthgamer, and Raghavendra (APPROX’10) presented an algorithm that yields a factor-2 2k approximation in time 2 O(k ) · n O(1 ). Later, Gupta, Talwar, and Witmer (STOC’13) showed how to obtain a 2-approximation algorithm with a blown-up runtime 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 ) · n O(1 ). In this article, 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 ) ·n O(1 ), directly improving the work of Chlamtáč et al. while keeping the runtime single-exponential in k. (ii) For any ε ∈ (0, 1], a factor-O(1/ε 2) approximation whose runtime is 2 O( k 1+ ε /ε ) · n O(1 ), implying a constant-factor approximation whose runtime is nearly single-exponential in k and a factor-O(log 2 k) approximation in time k O(k ) · n O(1 ). Key to these results is a new measure of a tree decomposition that we call combinatorial diameter, which may be of independent interest.Description
| openaire: EC/H2020/759557/EU//ALGOCom
Keywords
Other note
Citation
Chalermsook, P, Kaul, M, Mnich, M, Spoerhase, J, Uniyal, S & Vaz, D 2024, ' Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter ', ACM Transactions on Algorithms, vol. 20, no. 1, 6, pp. 1-20 . https://doi.org/10.1145/3632623