Parameterized Algorithms for the H-Packing with t-Overlap Problem

Abstract

We introduce the k-H-Packing with t-Overlap problem to formalize the problem of discovering overlapping communities in real networks. More precisely, in the k-H-Packing with t-Overlap problem, we search in a graph G for at least k subgraphs each isomorphic to a graph H such that any pair of subgraphs shares at most t vertices. In contrast with previous work where communities are disjoint, we regulate the overlap through a variable t. Our focus is on the parameterized complexity of the k-H-Packing with t-Overlap problem. Here, we provide a new technique for this problem generalizing the crown decomposition technique [B. Chor, M. Fellows, D. Juedes, WG 2004]. Using our global rule, we achieve a kernel with size bounded by 2(rk−r) for the k-K_r-Packing with (r−2)-Overlap problem. That is, when H is a clique of size r and t=r−2. In addition, we introduce the first parameterized algorithm for the k-H-Packing with t-Overlap problem when H is an arbitrary graph of size r. Our algorithm combines a bounded search tree with a greedy localization technique and runs in time O(r^rkk^{(r−t−1)k+2}n^r), where n=|V(G)|, r=|V(H)|, and t < r. Finally, we apply this search tree algorithm to the kernel obtained for the k-K_r-Packing with (r−2)-Overlap problem, and we show that this approach is faster than applying a brute-force algorithm in the kernel. In all our results, r and t are constants.