2014/11/25 by Henning Fernau, Fernau, Henning, Alejandro López-Ortíz +3
Business, Management and Accounting · Computer Science · Engineering · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #Sustainable Supply Chain Management
paper · pdf · doi:10.48550/arxiv.1411.6915
openalex publication_date 2014/11/25 · openalex created_date 2022/09/14 · openalex updated_date 2026/07/28
We consider the problem of discovering overlapping communities in networks\nwhich we model as generalizations of Graph Packing problems with overlap.\n We seek a collection \S' \⊆ \S consisting of at\nleast k sets subject to certain disjointness restrictions. In the r-Set\nPacking with t-Membership, each element of \U belongs to at most\nt sets of \S' while in t-Overlap each pair of sets in\n\S' overlaps in at most t elements. Each set of \S has\nat most r elements.\n Similarly, both of our graph packing problems seek a collection \K\nof at least k subgraphs in a graph G each isomorphic to a graph H \∈\n\H. In \H-Packing with t-Membership, each vertex of G\nbelongs to at most t subgraphs of \K while in t-Overlap each\npair of subgraphs in \K overlaps in at most t vertices. Each\nmember of \H has at most r vertices and m edges.\n We show NP-Completeness results for all of our packing problems and we give a\ndichotomy result for the \H-Packing with t-Membership problem\nanalogous to the Kirkpatrick and Hell citeKirk78. We reduce the r-Set\nPacking with t-Membership to a problem kernel with O((r+1)r kr)\nelements while we achieve a kernel with O(rr kr-t-1) elements for the\nr-Set Packing with t-Overlap. In addition, we reduce the\n\H-Packing with t-Membership and its edge version to problem\nkernels with O((r+1)r kr) and O((m+1)m k^m) vertices,\nrespectively. On the other hand, we achieve kernels with O(rr kr-t-1) and\nO(mm km-t-1) vertices for the \H-Packing with t-Overlap\nand its edge version, respectively. In all cases, k is the input parameter\nwhile t, r, and m are constants.\n