Kernelization algorithms for packing problems allowing overlaps

DOI10.1007/978-3-319-17142-5_35zbMATH Open1460.68074arXiv1411.6915OpenAlexW1588413154MaRDI QIDQ2948487FDOQ2948487

Authors: Henning Fernau, Jazmín Romero, Alejandro Lopez-Ortiz 

Publication date: 30 September 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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}^{\prime }subseteqmathcalS$ consisting of at least $k$ sets subject to certain disjointness restrictions. In the $r$-Set Packing with $t$-Membership, each element of $mathcalU$ belongs to at most $t$ sets of $mathcal{S}^{\prime }$ while in $t$-Overlap each pair of sets in $mathcal{S}^{\prime }$ overlaps in at most $t$ elements. Each set of $mathcalS$ has at most $r$ elements. Similarly, both of our graph packing problems seek a collection $mathcalK$ of at least $k$ subgraphs in a graph $G$ each isomorphic to a graph $HinmathcalH$. In $mathcalH$-Packing with $t$-Membership, each vertex of $G$ belongs to at most $t$ subgraphs of $mathcalK$ while in $t$-Overlap each pair of subgraphs in $mathcalK$ overlaps in at most $t$ vertices. Each member of $mathcalH$ 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 $mathcalH$-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 $mathcalH$-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 $mathcalH$-Packing with $t$-Overlap and its edge version, respectively. In all cases, $k$ is the input parameter while $t$, $r$, and $m$ are constants.

Full work available at URL: https://arxiv.org/abs/1411.6915

Recommendations

• Using parametric transformations toward polynomial kernels for packing problems allowing overlaps
• Parameterized algorithms for the \(H\)-packing with \(t\)-overlap problem
• A parameterized algorithm for packing overlapping subgraphs
• The \({\mathcal{G}}\)-packing with \(t\)-overlap problem
• Arbitrary overlap constraints in graph packing problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• A Problem Kernelization for Graph Packing
• On the completeness of a generalized matching problem
• Graph-Theoretic Concepts in Computer Science
• Looking at the stars
• Graph-based data clustering with overlaps
• Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
• Kernelization of packing problems
• A parameterized perspective on packing paths of length two
• Kernelization algorithms for packing problems allowing overlaps
• An improved kernelization algorithm for \(r\)-set packing
• Faster fixed-parameter tractable algorithms for matching and packing problems
• Another look at the degree constrained subgraph problem
• Uniform kernelization complexity of hitting forbidden minors
• A parameterized algorithm for packing overlapping subgraphs
• The \({\mathcal{G}}\)-packing with \(t\)-overlap problem

Cited In (15)

• Scheduling split intervals with non-uniform demands
• Parameterized algorithms for the \(H\)-packing with \(t\)-overlap problem
• The \({\mathcal{G}}\)-packing with \(t\)-overlap problem
• A parameterized algorithm for packing overlapping subgraphs
• Fast algorithms for parameterized problems with relaxed disjointness constraints
• Kernelization of cycle packing with relaxed disjointness constraints
• Stronger bounds and faster algorithms for packing in generalized kernel systems
• An improved kernelization for \(P_{2}\)-packing
• An improved kernelization algorithm for \(r\)-set packing
• Using parametric transformations toward polynomial kernels for packing problems allowing overlaps
• Explicit linear kernels for packing problems
• Arbitrary overlap constraints in graph packing problems
• Kernelization algorithms for packing problems allowing overlaps
• Kernels for packing and covering problems
• Kernels for Packing and Covering Problems

This page was built for publication: Kernelization algorithms for packing problems allowing overlaps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2948487)