Projects per year
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 nvertex graphs G of treewidth k, Chlamtáč, Krauthgamer, and Raghavendra (APPROX’10) presented an algorithm that yields a factor2 ^{2k} approximation in time 2 ^{O}(k ^{)} · n ^{O}(1 ^{)}. Later, Gupta, Talwar, and Witmer (STOC’13) showed how to obtain a 2approximation algorithm with a blownup 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 factor2 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 factorO(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 singleexponential in k. (ii) For any ε ∈ (0, 1], a factorO(1/ε ^{2}) approximation whose runtime is 2 ^{O}( ^{k} ^{1}+ ^{ε} ^{/}ε ^{)} · n ^{O}(1 ^{)}, implying a constantfactor approximation whose runtime is nearly singleexponential in k and a factorO(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 language  English 

Article number  6 
Pages (fromto)  120 
Journal  ACM Transactions on Algorithms 
Volume  20 
Issue number  1 
Early online date  2023 
DOIs  
Publication status  Published  22 Jan 2024 
MoE publication type  A1 Journal articlerefereed 
Fingerprint
Dive into the research topics of 'Approximating Sparsest Cut in LowTreewidth Graphs via Combinatorial Diameter'. Together they form a unique fingerprint.Projects
 2 Finished

ALGOCom: Novel Algorithmic Techniques through the Lens of Combinatorics
Chalermsook, P., Jindal, G., Franck, M., Jiamjitrak, W., Khodamoradi, K., Yingchareonthawornchai, S., Gadekar, A., Orgo, L. & Spoerhase, J.
01/02/2018 → 31/01/2024
Project: EU: ERC grants

Combinatorics of Graph Packing and Online Binary Search Trees
Chalermsook, P., Franck, M., Jiamjitrak, W., Uniyal, S., Obscura Acosta, N. & Gadekar, A.
01/09/2017 → 31/08/2022
Project: Academy of Finland: Other research funding