“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 16490
School of Mathematics
  Title:   Multi-way sparsest cut problem on trees with a control on the number of parts and outliers
  Author(s):  Ramin Javadi (Joint with S. Ashkboos)
  Status:   Published
  Journal: Discrete Appl. Math.
  Vol.:  289
  Year:  2021
  Pages:   281-291
  Supported by:  IPM
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(k2 n3) , 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.

Download TeX format
back to top
scroll left or right