On the parameterized complexity of Sparsest Cut and Small-Set Expansion problems.

We present a parameterized dichotomy for the k - Sparsest Cut problem in weighted and unweighted versions. In particular, we show that the weighted k - Sparsest Cut problem is NP-hard for every k ≥ 3 even on graphs with bounded vertex cover number. Also, the unweighted k - Sparsest Cut problem is W[1]-hard when parameterized by the three combined parameters tree-depth, feedback vertex set number, and k. On the positive side, we show that the unweighted k - Sparsest Cut problem is FPT when parameterized by the vertex cover number and k , and when k is fixed, it is FPT with respect to the treewidth. Moreover, we show that the generalized version κ - Small-Set Expansion problem is FPT when parameterized by κ and the maximum degree of the graph, though it is W[1]-hard for each of these parameters separately. [ABSTRACT FROM AUTHOR]