On the Parameterized Complexity of Sparsest Cut and Small-set Expansion Problems

Ramin Javadi, Amir Nikabadi

We present a parameterized dichotomy for the \textsc{$k$-Sparsest Cut} problem in weighted and unweighted versions. In particular, we show that the weighted \textsc{$k$-Sparsest Cu…