Arbitrary overlap constraints in graph packing problems

DOI10.1142/S0129054118500053MaRDI QIDQ4639933zbMATH OpenOpenAlexWikidataFDO

Authors Cynthia B. Perez, Jazmín Romero, Alejandro Lopez-Ortiz

Publication date 14 May 2018

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

fixed-parameter algorithmgraph packingoverlapping communitiesset packing

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: In earlier versions of the community discovering problem, the overlap between communities was restricted by a simple count upper-bound [17,5,11,8]. In this paper, we introduce the $Pi$-Packing with $alpha()$-Overlap problem to allow for more complex constraints in the overlap region than those previously studied. Let $mathcal{V}^r$ be all possible subsets of vertices of $V(G)$ each of size at most $r$, and $alpha:mathcal{V}^{r}imesmathcal{V}^{r}o0,1$ be a function. The $Pi$-Packing with $alpha()$-Overlap problem seeks at least $k$ induced subgraphs in a graph $G$ subject to: (i) each subgraph has at most $r$ vertices and obeys a property $Pi$, and (ii) for any pair $H_i,H_j$, with $ieqj$, $alpha(H_i,H_j)=0$ (i.e., $H_i,H_j$ do not conflict). We also consider a variant that arises in clustering applications: each subgraph of a solution must contain a set of vertices from a given collection of sets $mathcalC$, and no pair of subgraphs may share vertices from the sets of $mathcalC$. In addition, we propose similar formulations for packing hypergraphs. We give an $O(r^{rk}{k}^{(r+1)k}{n}^{cr})$ algorithm for our problems where $k$ is the parameter and $c$ and $r$ are constants, provided that: i) $Pi$ is computable in polynomial time in $n$ and ii) the function $alpha()$ satisfies specific conditions. Specifically, $alpha()$ is hereditary, applicable only to overlapping subgraphs, and computable in polynomial time in $n$. Motivated by practical applications we give several examples of $alpha()$ functions which meet those conditions.

Recommendations

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

Cites work

• A classification for community discovery methods in complex networks
• A Problem Kernelization for Graph Packing
• An improved kernelization algorithm for \(r\)-set packing
• Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
• Clustering Social Networks
• Defining and discovering communities in social networks
• Graph minors. XX: Wagner's conjecture
• Graph-Theoretic Concepts in Computer Science
• Kernelization of cycle packing with relaxed disjointness constraints
• Looking at the stars
• On the complexity of submap isomorphism and maximum common submap problems
• Overlapping community detection in networks
• Packing paths: recycling saves time
• Parameterized algorithms for the H-packing with t-overlap problem
• Using parametric transformations toward polynomial kernels for packing problems allowing overlaps

Cited in

(5)

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

This page was built for publication: Arbitrary overlap constraints in graph packing problems

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