On the complexity of isoperimetric problems on trees

DOI10.1016/J.DAM.2011.08.015zbMATH Open1237.05042arXiv1009.0706OpenAlexW1655771767MaRDI QIDQ765346FDOQ765346

Ramin Javadi, Amir Daneshgar

Publication date: 19 March 2012

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

Abstract: This paper is aimed to investigate some computational aspects of different isoperimetric problems on weighted trees. In this regard, we consider different connectivity parameters called {it minimum normalized cuts}/{it isoperimteric numbers} defined through taking minimum of the maximum or the mean of the normalized outgoing flows from a set of subdomains of vertices, where these subdomains constitute a {it partition}/{it subpartition}. Following the main result of [A. Daneshgar, {it et. al.}, {it On the isoperimetric spectrum of graphs and its approximations}, JCTB, (2010)], it is known that the isoperimetric number and the minimum normalized cut both can be described as $0,1$-optimization programs, where the latter one does {it not} admit a relaxation to the reals. We show that the decision problem for the case of taking $k$-partitions and the maximum (called the max normalized cut problem { m NCP}${}^M$) as well as the other two decision problems for the mean version (referred to as { m IPP}${}^m$ and { m NCP}${}^m$) are $NP$-complete problems. On the other hand, we show that the decision problem for the case of taking $k$-subpartitions and the maximum (called the max isoperimetric problem { m IPP}${}^M$) can be solved in {it linear time} for any weighted tree and any $kgeq2$. Based on this fact, we provide polynomial time $O(k)$-approximation algorithms for all different versions of $k$th isoperimetric numbers considered. Moreover, when the number of partitions/subpartitions, $k$, is a fixed constant, as an extension of a result of B. Mohar (1989) for the case $k=2$ (usually referred to as the Cheeger constant), we prove that max and mean isoperimetric numbers of weighted trees as well as their max normalized cut can be computed in polynomial time. We also prove some hardness results for the case of simple unweighted graphs and trees.

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

Recommendations

• Computing the isoperimetric number of a graph
• A shifting algorithm for constrained min-max partition on trees
• scientific article; zbMATH DE number 3956440
• On the complexity of graph tree partition problems.
• Min Cut is NP-complete for edge weighted trees

zbMATH Keywords

computational complexityapproximation algorithmsCheeger constantgraph partitioningweighted treesnormalized cutisoperimetric number

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Isoperimetric numbers of graphs
• Succinct representation of balanced parentheses and static trees
• Algorithmic Aspects of Graph Connectivity
• Title not available (Why is that?)
• Expander flows, geometric embeddings and graph partitioning
• On the isoperimetric spectrum of graphs and its approximations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph Clustering and Minimum Cut Trees
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
• Discrete groups, expanding graphs and invariant measures. With an appendix by Jonathan D. Rogawski
• The shifting algorithm technique for the partitioning of trees
• On nodal domains and higher-order Cheeger inequalities of finite reversible Markov processes
• Weighted graph Laplacians and isoperimetric inequalities
• Computing sharp bounds for hard clustering problems on trees
• EFFICIENT APPROXIMATION ALGORITHMS FOR PAIRWISE DATA CLUSTERING AND APPLICATIONS
• Breaking the multicommodity flow barrier for o(√log n)-approximations to sparsest cut
• Minimum cost subpartitions in graphs

Cited In (8)

• On the parameterized complexity of \textsc{Sparsest Cut} and \textsc{Small-Set Expansion} problems
• Multi-way sparsest cut problem on trees with a control on the number of parts and outliers
• A note on isoperimetric peaks of complete trees
• Computing the isoperimetric number of a graph
• Mean isoperimetry with control on outliers: exact and approximation algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• Clustering and outlier detection using isoperimetric number of trees

This page was built for publication: On the complexity of isoperimetric problems on trees

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