Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter

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

Research output: Contribution to journalArticleScientificpeer-review

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.

Original languageEnglish
Article number6
Pages (from-to)1-20
JournalACM Transactions on Algorithms
Volume20
Issue number1
Early online date2023
DOIs
Publication statusPublished - 22 Jan 2024
MoE publication typeA1 Journal article-refereed

Fingerprint

Dive into the research topics of 'Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter'. Together they form a unique fingerprint.

Cite this