Title: Multi-way sparsest cut problem on trees with a control on the number of parts and outliers,
Abstract: 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 generalization of this problem seeking for $ k $ disjoint
subsets of vertices (clusters) whose all edge expansions are small and
furthermore, the number of vertices remained in the exterior of the subsets
(outliers) is also small. We prove that although this problem is $ NP-$hard for
trees, it can be solved in polynomial time for all weighted trees, provided
that we restrict the search space to subsets which induce connected subgraphs.
The proposed algorithm is based on dynamic programming and runs in the worst
case in $ O(k^2 n^3) $, when $ n $ is the number of vertices and $ k $ is the
number of clusters. It also runs in linear time when the number of clusters and
the number of outliers is bounded by a constant.