| | |
| | |
Stat |
Members: 3643 Articles: 2'487'895 Articles rated: 2609
29 March 2024 |
|
| | | |
|
Article overview
| |
|
Kernelization Algorithms for Packing Problems Allowing Overlaps | Henning Fernau
; Alejandro López-Ortiz
; Jazmín Romero
; | Date: |
25 Nov 2014 | Abstract: | We consider the problem of discovering overlapping communities in networks
which we model as generalizations of the Set and Graph Packing problems with
overlap.
As usual for Set Packing problems we seek a collection $mathcal{S}$
consisting of at least $k$ sets subject to certain disjointness restrictions.
In a Set Packing with $t$-Membership, each element of $mathcal{U}$ belongs to
at most $t$ sets while in a Set Packing with $t$-Overlap each pair of sets
overlaps in at most $t$ elements. For both problems, each set of $mathcal{S}$
has at most $r$ elements, and $t$ and $r$ are constants.
Similarly, both of our graph packing problems seek a collection of at least
$k$ subgraphs in a graph $G$ each isomorphic to a graph $H in mathcal{H}$. In
an $mathcal{H}$-Packing with $t$-Membership, each vertex of $G$ belongs to at
most $t$ subgraphs while in an $mathcal{H}$-Packing with $t$-Overlap each pair
of subgraphs overlaps in at most $t$ vertices. For both problems, each member
of $mathcal{H}$ has at most $r$ vertices, and $t$ and $r$ are constants.
We provide NP-Completeness results for all of our packing problems. Given
that, we reduce the Set Packing with $t$-Overlap to an $O(r^r k^{r-t-1})$
problem kernel while we achieve an $O(r^r k^{r-1})$ problem kernel for the Set
Packing with $t$-Membership. In addition, we reduce the $mathcal{H}$-Packing
with $t$-Membership and its induced version to an $O(r^r k^{r-1})$ kernel.
Moreover, we give an $O(r^{2r^2} k^{{r^2}-1})$ kernel for its edge version. On
the other hand, we achieve an $O(r^r k^{r-t-1})$ kernel for the
$mathcal{H}$-Packing with $t$-Overlap and its induced version while we provide
an $O(r^{2r^2} k^{r^2-t-1})$ kernel for its edge version. Our kernel results
match the best kernel for Set and Graph Packing. | Source: | arXiv, 1411.6915 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |