RECORD
Kernelization Algorithms for Packing Problems Allowing Overlaps (Extended Version)
Data Structures and Algorithms · Submitted 25 Nov 2014
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We reduce the $r$-Set Packing with $t$-Membership to a problem kernel with $O((r+1)^r k^{r})$ elements while we achieve a kernel with $O(r^r k^{r-t-1})$ elements for the $r$-Set Packing with $t$-Overlap.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
We consider the problem of discovering overlapping communities in networks which we model as generalizations of Graph Packing problems with overlap. We seek a collection $\mathcal{S}' \subseteq \mathcal{S}$ consisting of at least $k$ sets subject to certain disjointness restrictions. In the $r$-Set Packing with $t$-Membership, each element of $\mathcal{U}$ belongs to at most $t$ sets of $\mathcal{S'}$ while in $t$-Overlap each pair of sets in $\mathcal{S'}$ overlaps in at most $t$ elements. Each set of $\mathcal{S}$ has at most $r$ elements. Similarly, both of our graph packing problems seek a collection $\mathcal{K}$ of at least $k$ subgraphs in a graph $G$ each isomorphic to a graph $H \in \mathcal{H}$. In $\mathcal{H}$-Packing with $t$-Membership, each vertex of $G$ belongs to at most $t$ subgraphs of $\mathcal{K}$ while in $t$-Overlap each pair of subgraphs in $\mathcal{K}$ overlaps in at most $t$ vertices. Each member of $\mathcal{H}$ has at most $r$ vertices and $m$ edges. We show NP-Completeness results for all of our packing problems and we give a dichotomy result for the $\mathcal{H}$-Packing with $t$-Membership problem analogous to the Kirkpatrick and Hell \cite{Kirk78}. We reduce the $r$-Set Packing with $t$-Membership to a problem kernel with $O((r+1)^r k^{r})$ elements while we achieve a kernel with $O(r^r k^{r-t-1})$ elements for the $r$-Set Packing with $t$-Overlap. In addition, we reduce the $\mathcal{H}$-Packing with $t$-Membership and its edge version to problem kernels with $O((r+1)^r k^{r})$ and $O((m+1)^{m} k^{{m}})$ vertices, respectively. On the other hand, we achieve kernels with $O(r^r k^{r-t-1})$ and $O(m^{m} k^{m-t-1})$ vertices for the $\mathcal{H}$-Packing with $t$-Overlap and its edge version, respectively. In all cases, $k$ is the input parameter while $t$, $r$, and $m$ are constants.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We consider the problem of discovering overlapping communities in networks which we model as generalizations of Graph Packing problems with overlap. | background 0.69 | 0.60 | 0.03 | asserted 0.96 |
| s1 | We seek a collection $\mathcal{S}' \subseteq \mathcal{S}$ consisting of at least $k$ sets subject to certain disjointness restrictions. | background 0.78 | 0.47 | 0.03 | asserted 0.90 |
| s2 | In the $r$-Set Packing with $t$-Membership, each element of $\mathcal{U}$ belongs to at most $t$ sets of $\mathcal{S'}$ while in $t$-Overlap each pair of sets in $\mathcal{S'}$ overlaps in at most $t$ elements. | background 0.80 | 0.18 | 0.04 | asserted 0.99 |
| s3 | Each set of $\mathcal{S}$ has at most $r$ elements. | background 0.97 | 0.14 | 0.02 | asserted 1.00 |
| s4 | Similarly, both of our graph packing problems seek a collection $\mathcal{K}$ of at least $k$ subgraphs in a graph $G$ each isomorphic to a graph $H \in \mathcal{H}$. | background 0.56 | 0.54 | 0.03 | asserted 1.00 |
| s5 | In $\mathcal{H}$-Packing with $t$-Membership, each vertex of $G$ belongs to at most $t$ subgraphs of $\mathcal{K}$ while in $t$-Overlap each pair of subgraphs in $\mathcal{K}$ overlaps in at most $t$ vertices. | background 0.73 | 0.38 | 0.03 | asserted 0.99 |
| s6 | Each member of $\mathcal{H}$ has at most $r$ vertices and $m$ edges. | background 0.93 | 0.18 | 0.02 | asserted 1.00 |
| s7 | We show NP-Completeness results for all of our packing problems and we give a dichotomy result for the $\mathcal{H}$-Packing with $t$-Membership problem analogous to the Kirkpatrick and Hell \cite{Kirk78}. | result 0.83 | 0.93 | 0.15 | asserted 1.00 |
| s8 | We reduce the $r$-Set Packing with $t$-Membership to a problem kernel with $O((r+1)^r k^{r})$ elements while we achieve a kernel with $O(r^r k^{r-t-1})$ elements for the $r$-Set Packing with $t$-Overlap. | result 0.83 | 0.96 | 0.43 | asserted 1.00 |
| s9 | In addition, we reduce the $\mathcal{H}$-Packing with $t$-Membership and its edge version to problem kernels with $O((r+1)^r k^{r})$ and $O((m+1)^{m} k^{{m}})$ vertices, respectively. | result 0.87 | 0.95 | 0.17 | asserted 1.00 |
| s10 | On the other hand, we achieve kernels with $O(r^r k^{r-t-1})$ and $O(m^{m} k^{m-t-1})$ vertices for the $\mathcal{H}$-Packing with $t$-Overlap and its edge version, respectively. | result 0.94 | 0.95 | 0.19 | asserted 1.00 |
| s11 | In all cases, $k$ is the input parameter while $t$, $r$, and $m$ are constants. | background 0.50 | 0.41 | 0.05 | asserted 0.99 |
What was examined, and what was not
- arXiv listing abstract v3
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
We consider the problem of discovering overlapping communities in networks which we model as generalizations of Graph Packing problems with overlap. We seek a collection $\mathcal{S}' \subseteq \mathcal{S}$ consisting of at least $k$ sets subject to certain disjointness restrictions. In the $r$-Set Packing with $t$-Membership, each element of $\mathcal{U}$ belongs to at most $t$ sets of $\mathcal{S'}$ while in $t$-Overlap each pair of sets in $\mathcal{S'}$ overlaps in at most $t$ elements. Each set of $\mathcal{S}$ has at most $r$ elements. Similarly, both of our graph packing problems seek a collection $\mathcal{K}$ of at least $k$ subgraphs in a graph $G$ each isomorphic to a graph $H \in \mathcal{H}$. In $\mathcal{H}$-Packing with $t$-Membership, each vertex of $G$ belongs to at most $t$ subgraphs of $\mathcal{K}$ while in $t$-Overlap each pair of subgraphs in $\mathcal{K}$ overlaps in at most $t$ vertices. Each member of $\mathcal{H}$ has at most $r$ vertices and $m$ edges. We show NP-Completeness results for all of our packing problems and we give a dichotomy result for the $\mathcal{H}$-Packing with $t$-Membership problem analogous to the Kirkpatrick and Hell \cite{Kirk78}. We reduce the $r$-Set Packing with $t$-Membership to a problem kernel with $O((r+1)^r k^{r})$ elements while we achieve a kernel with $O(r^r k^{r-t-1})$ elements for the $r$-Set Packing with $t$-Overlap. In addition, we reduce the $\mathcal{H}$-Packing with $t$-Membership and its edge version to problem kernels with $O((r+1)^r k^{r})$ and $O((m+1)^{m} k^{{m}})$ vertices, respectively. On the other hand, we achieve kernels with $O(r^r k^{r-t-1})$ and $O(m^{m} k^{m-t-1})$ vertices for the $\mathcal{H}$-Packing with $t$-Overlap and its edge version, respectively. In all cases, $k$ is the input parameter while $t$, $r$, and $m$ are constants.
Human review
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.