Parameterized Algorithms for the H-Packing with t-Overlap Problem
Alejandro López-Ortiz and Jazmín Romero
Vol. 18, no. 4, pp. 515-538, 2014. Regular paper.
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(rkr) for the k-Kr-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(rrkk(rt−1)k+2nr), where n=|V(G)|, r=|V(H)|, and t < r. Finally, we apply this search tree algorithm to the kernel obtained for the k-Kr-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.
Submitted: March 2014.
Reviewed: June 2014.
Revised: July 2014.
Accepted: July 2014.
Final: December 2014.
Published: December 2014.
article (PDF)