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

Alejandro López-Ortiz ; Jazmín Romero

Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Eighth International Workshop on Algorithms and Computation, WALCOM 2014 , Tome 18 (2014) no. 4, pp. 515-538.

Résumé

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-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(r−t−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.

Détail

DOI : 10.7155/jgaa.00335