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 kappa-SMALL-SET EXPANSION problem is FPT when parameterized by kappa and the maximum degree of the graph, though it is W[1]-hard for each of these parameters separately. (c) 2024 Elsevier B.V. All rights reserved.