Source author record

Jazmín Romero

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms

Catalog footprint

Research overview

2works

1topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Arbitrary Overlap Constraints in Graph Packing Problems

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 $Π$ -Packing with $α()$ -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 $α: \mathcal{V}^r \times \mathcal{V}^r \to \{0,1\}$ be a function. The $Π$ -Packing with $α()$ -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 $Π$ , and (ii) for any pair $H_i,H_j$ , with $i\neq j$ , $α(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 $\mathcal{C}$ , and no pair of subgraphs may share vertices from the sets of $\mathcal{C}$ . 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) $Π$ is computable in polynomial time in $n$ and ii) the function $α()$ satisfies specific conditions. Specifically, $α()$ is hereditary, applicable only to overlapping subgraphs, and computable in polynomial time in $n$ . Motivated by practical applications we give several examples of $α()$ functions which meet those conditions.

preprint2015arXiv

Kernelization Algorithms for Packing Problems Allowing Overlaps (Extended Version)

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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.