On the complexity of isoperimetric problems on trees

DOI10.1016/J.DAM.2011.08.015MaRDI QIDQ765346zbMATH OpenOpenAlexFDO

Authors Amir Daneshgar, Ramin Javadi

Publication date 19 March 2012

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3680356 (Why is no real title available?)
• scientific article; zbMATH DE number 18980 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2060183 (Why is no real title available?)
• Algorithmic Aspects of Graph Connectivity
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation and inaproximability results on balanced connected partitions of graphs
• Breaking the multicommodity flow barrier for o(√log n)-approximations to sparsest cut
• Computing sharp bounds for hard clustering problems on 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
• EFFICIENT APPROXIMATION ALGORITHMS FOR PAIRWISE DATA CLUSTERING AND APPLICATIONS
• Expander flows, geometric embeddings and graph partitioning
• Graph Clustering and Minimum Cut Trees
• Graph theory
• Isoperimetric numbers of graphs
• Minimum cost subpartitions in graphs
• On nodal domains and higher-order Cheeger inequalities of finite reversible Markov processes
• On the isoperimetric spectrum of graphs and its approximations
• Succinct representation of balanced parentheses and static trees
• The shifting algorithm technique for the partitioning of trees
• Weighted graph Laplacians and isoperimetric inequalities

Cited in

(10)

• On the isoperimetric spectrum of graphs and its approximations
• On the parameterized complexity of \textsc{Sparsest Cut} and \textsc{Small-Set Expansion} problems
• Bounds on isoperimetric values of trees
• Clustering and outlier detection using isoperimetric number of trees
• Computing the isoperimetric number of a graph
• scientific article; zbMATH DE number 1335884 (Why is no real title available?)
• scientific article; zbMATH DE number 6820278 (Why is no real title available?)
• Mean isoperimetry with control on outliers: exact and approximation algorithms
• 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

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)