Home  Issues  Aims and Scope  Instructions for Authors 
Special Issue on Selected Papers from the Eighth International Workshop on Algorithms and Computation, WALCOM 2014
DOI: 10.7155/jgaa.00335
Parameterized Algorithms for the HPacking with tOverlap Problem
Alejandro LópezOrtiz and
Jazmín Romero
Vol. 18, no. 4, pp. 515538, 2014. Regular paper.
Abstract We introduce the kHPacking with tOverlap problem to formalize the problem of discovering overlapping communities in real networks. More precisely, in the kHPacking with tOverlap 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 kHPacking with tOverlap 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 kK_{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 kHPacking with tOverlap 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^{rk}k^{(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 kK_{r}Packing with (r−2)Overlap problem, and we show that this approach is faster than applying a bruteforce 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.
