Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter

Parinya Chalermsook, Matthias Kaul, Matthias Mnich, Joachim Spoerhase, Sumedha Uniyal, Daniel Vaz

Tutkimustuotos: LehtiartikkeliArticleScientificvertaisarvioitu

Abstrakti

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.

AlkuperäiskieliEnglanti
Artikkeli6
Sivut1-20
JulkaisuACM Transactions on Algorithms
Vuosikerta20
Numero1
Varhainen verkossa julkaisun päivämäärä2023
DOI - pysyväislinkit
TilaJulkaistu - 22 tammik. 2024
OKM-julkaisutyyppiA1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä

Sormenjälki

Sukella tutkimusaiheisiin 'Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä