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)$-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)\le p$. Our first result shows that if $μ$ is an {\em arbitrary} polynomial-time computable monotone function, then $(μ,p,q)$-PARTITION can be solved in time $n^{O(q)}$, i.e., it is polynomial-time solvable {\em 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)$-PARTITION can be solved in time $2^{O(p)}\cdot n^{O(1)}$ and in time $2^{O(q)}\cdot n^{O(1)}$ on $n$-vertex graphs, i.e., the problem is fixed-parameter tractable parameterized by $p$ or by $q$.