On the complexity of isoperimetric problems on trees

AbstractThis paper is aimed at investigating some computational aspects of different isoperimetric problems on weighted trees. In this regard, we consider different connectivity parameters called minimum normalized cuts/isoperimetric numbers defined through taking the minimum of the maximum or the mean of the normalized outgoing flows from a set of subdomains of vertices, where these subdomains constitute a partition/subpartition. We show that the decision problem for the case of taking k-partitions and the maximum (called the max normalized cut problem NCPM), and the other two decision problems for the mean version (referred to as IPPm and NCPm) are NP-complete problems for weighted trees. 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 IPPM) can be solved in linear time for any weighted tree and any k≥2. On the basis of this fact, we provide polynomial time O(k)-approximation algorithms for all different versions of the kth isoperimetric numbers considered.Moreover, for when the number of partitions/subpartitions, k, is a fixed constant, we prove, as an extension of a result of Mohar (1989) [20] for the case k=2 (usually referred to as the Cheeger constant), that the max and mean isoperimetric numbers of weighted trees, and their max minimum normalized cut can be computed in polynomial time. We also prove some hardness results for the case of simple unweighted graphs and trees