  We give a 2-approximation algorithm for Non-Uniform Sparsest Cut that runs in
time $n^{O(k)}$, where $k$ is the treewidth of the graph. This improves on the
previous $2^{2^k}$-approximation in time $\poly(n) 2^{O(k)}$ due to
Chlamt\'a\v{c} et al.
  To complement this algorithm, we show the following hardness results: If the
Non-Uniform Sparsest Cut problem has a $\rho$-approximation for series-parallel
graphs (where $\rho \geq 1$), then the Max Cut problem has an algorithm with
approximation factor arbitrarily close to $1/\rho$. Hence, even for such
restricted graphs (which have treewidth 2), the Sparsest Cut problem is NP-hard
to approximate better than $17/16 - \epsilon$ for $\epsilon > 0$; assuming the
Unique Games Conjecture the hardness becomes $1/\alpha_{GW} - \epsilon$. For
graphs with large (but constant) treewidth, we show a hardness result of $2 -
\epsilon$ assuming the Unique Games Conjecture.
  Our algorithm rounds a linear program based on (a subset of) the
Sherali-Adams lift of the standard Sparsest Cut LP. We show that even for
treewidth-2 graphs, the LP has an integrality gap close to 2 even after
polynomially many rounds of Sherali-Adams. Hence our approach cannot be
improved even on such restricted graphs without using a stronger relaxation.
