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 {rm NCP}$^M$) as well as the other two decision problems for the mean version (referred to as {rm IPP}$^m$ and {rm 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 {rm IPP}$^M$) can be solved in {it linear time} for any weighted tree and any $k geq 2$. Based on this fact, we provide polynomial time $O(k)$-approximation algorithms for all differe
Download