Options
Approximating sparsest cut in low-treewidth graphs via combinatorial diameter
Publikationstyp
Journal Article
Date Issued
2024-01-22
Sprache
English
Journal
Volume
20
Issue
1
Article Number
6
Citation
ACM Transactions in Algorithms (2024)
Publisher DOI
Scopus ID
Publisher
Association for Computing Machinery (ACM)
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 2010) presented an algorithm that yields a factor-22k approximation in time 2O(k) · nO(1). Later, Gupta, Talwar and Witmer (STOC 2013) showed how to obtain a 2-approximation algorithm with a blown-up run time of nO(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 2O(k) · nO(1).
In this paper, we make significant progress towards this goal, via the following results:
(i)
A factor-O(k2) approximation that runs in time 2O(k) · nO(1), directly improving the work of Chlamtáč et al. while keeping the run time single-exponential in k.
(ii)
For any ε ∈ (0, 1], a factor-O(1/ε2) approximation whose run time is 2O(k1+ε/ε)⋅nO(1), implying a constant-factor approximation whose run time is nearly single-exponential in k and a factor-O(log 2k) approximation in time kO(k) · nO(1).
Key to these results is a new measure of a tree decomposition that we call combinatorial diameter, which may be of independent interest.
In this paper, we make significant progress towards this goal, via the following results:
(i)
A factor-O(k2) approximation that runs in time 2O(k) · nO(1), directly improving the work of Chlamtáč et al. while keeping the run time single-exponential in k.
(ii)
For any ε ∈ (0, 1], a factor-O(1/ε2) approximation whose run time is 2O(k1+ε/ε)⋅nO(1), implying a constant-factor approximation whose run time is nearly single-exponential in k and a factor-O(log 2k) approximation in time kO(k) · nO(1).
Key to these results is a new measure of a tree decomposition that we call combinatorial diameter, which may be of independent interest.
Subjects
Parameterized Algorithms
Sparsest Cut
Treewidth
DDC Class
004: Computer Sciences
510: Mathematics
Version History
You are currently viewing version 1 of the item.