Multi-way sparsest cut problem on trees with a control on the number of parts and outliers

Ramin Javadi, Saleh Ashkboos

Given a graph, the sparsest cut problem asks for a subset of vertices whose edge expansion (the normalized cut given by the subset) is minimized. In this paper, we study a generali…