Clustering with local restrictions

We study a family of graph clustering problems where each cluster has to satisfy a certain local requirement. Formally, let μ be a function on the subsets of vertices of a graph G  . In the (μ,p,q)(μ,p,q)-Partition problem, the task is to find a partition of the vertices into clusters where each cluster C satisfies the requirements that (1) at most q edges leave C   and (2) μ(C)⩽pμ(C)⩽p. Our first result shows that if μ is an arbitrary   polynomial-time computable monotone function, then (μ,p,q)(μ,p,q)-Partition can be solved in time nO(q)nO(q), i.e., it is polynomial-time solvable for every fixed q. We study in detail three concrete functions μ   (the number of vertices in the cluster, number of nonedges in the cluster, maximum number of non-neighbors a vertex has in the cluster), which correspond to natural clustering problems. For these functions, we show that (μ,p,q)(μ,p,q)-Partition can be solved in time 2O(p)⋅nO(1)2O(p)⋅nO(1) and in time 2O(q)⋅nO(1)2O(q)⋅nO(1) on n-vertex graphs, i.e., the problem is fixed-parameter tractable parameterized by p or by q.