On the complexity of isoperimetric problems on trees

This 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 kk-partitions and the maximum (called the max normalized cut problem NCPMM), and the other two decision problems for the mean version (referred to as IPPmm and NCPmm) are NPNP-complete problems for weighted trees. On the other hand, we show that the decision problem for the case of taking kk-subpartitions and the maximum (called the max isoperimetric problem IPPMM) can be solved in linear time   for any weighted tree and any k≥2k≥2. On the basis of this fact, we provide polynomial time O(k)O(k)-approximation algorithms for all different versions of the kkth isoperimetric numbers considered.Moreover, for when the number of partitions/subpartitions, kk, is a fixed constant, we prove, as an extension of a result of Mohar (1989) [20] for the case k=2k=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.

► Computational aspects of generalized isoperimetric problems on weighted trees are investigated.
► The decision problem for the kkth maximum isoperimetric number (IPPMM) can be solved in linear time for weighted trees.
► The decision problems for the kkth mean isoperimetric number and the kkth minimum normalized cuts are NPNP-complete.
► XP algorithms are presented for determining the kkth max/mean isoperimetric numbers and the kkth max minimum normalized cuts.
► All of the corresponding decision problems are NPNP-complete for weighted bipartite graphs of tree-width at most 2.