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

DOI10.1016/J.DAM.2020.11.013MaRDI QIDQ2217481zbMATH OpenOpenAlexFDO

Authors Saleh Ashkboos, Ramin Javadi

Publication date 29 December 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.05570

zbMATH Keywords

computational complexityCheeger constantgraph partitioningweighted treesnormalized cutsparsest cut problemisoperimetric number

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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.

Recommendations

• On the generalized multiway cut in trees problem
• Approximation algorithm for sparsest \(k\)-partitioning
• On the generalized multiway cut in trees problem
• Multi-terminal cuts in generalized tree networks
• The complexity status of problems related to sparsest cuts

Cites work

• scientific article; zbMATH DE number 3877889 (Why is no real title available?)
• scientific article; zbMATH DE number 3793445 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Approximation algorithm for sparsest \(k\)-partitioning
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Clustering and outlier detection using isoperimetric number of trees
• Data Clustering: Theory, Algorithms, and Applications
• Eigenvalues and expanders
• Expander flows, geometric embeddings and graph partitioning
• Expander graphs and their applications
• Geometry and spectra of compact Riemann surfaces
• Graph-Theoretical Methods for Detecting and Describing Gestalt Clusters
• Isoperimetric constants and the first eigenvalue of a compact riemannian manifold
• Isoperimetric numbers of graphs
• On nodal domains and higher-order Cheeger inequalities of finite reversible Markov processes
• On the complexity of isoperimetric problems on trees
• On the hardness of approximating Multicut and Sparsest-Cut
• On the isoperimetric spectrum of graphs and its approximations
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators

Cited in

(1)

• Mean isoperimetry with control on outliers: exact and approximation algorithms

This page was built for publication: Multi-way sparsest cut problem on trees with a control on the number of parts and outliers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2217481)