Kernelization algorithms for packing problems allowing overlaps

DOI10.1007/978-3-319-17142-5_35MaRDI QIDQ2948487zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(15)

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

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)