  In the non-uniform sparsest cut problem, we are given a supply graph G and a
demand graph D, both with the same set of nodes V. The goal is to find a cut of
V that minimizes the ratio of the total capacity on the edges of G crossing the
cut over the total demand of the crossing edges of D. In this work, we study
the non-uniform sparsest cut problem for supply graphs with bounded treewidth
k. For this case, Gupta, Talwar and Witmer [STOC 2013] obtained a
2-approximation with polynomial running time for fixed k, and the question of
whether there exists a c-approximation algorithm for a constant c independent
of k, that runs in FPT time, remained open. We answer this question in the
affirmative. We design a 2-approximation algorithm for the non-uniform sparsest
cut with bounded treewidth supply graphs that runs in FPT time, when
parameterized by the treewidth. Our algorithm is based on rounding the optimal
solution of a linear programming relaxation inspired by the Sherali-Adams
hierarchy. In contrast to the classic Sherali-Adams approach, we construct a
relaxation driven by a tree decomposition of the supply graph by including a
carefully chosen set of lifting variables and constraints to encode information
of subsets of nodes with super-constant size, and at the same time we have a
sufficiently small linear program that can be solved in FPT time.
