<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T20:37:19Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/9975" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/9975</identifier><datestamp>2025-03-26T23:36:22Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9930</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="advisor">Lopez Ortiz, Alejandro</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="b9663a8d-76d5-4a73-8720-85cae2952739" confidence="600">Romero, Jazmin</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2015-11-12T13:26:35Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2015-11-12T13:26:35Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2015-11-12</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2015-10-26</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/9975</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">Many complex systems that exist in nature and society can be expressed in terms of networks (e.g.,&#xd;
social networks, communication networks, biological networks, Web graph, among others). Usually a node&#xd;
represents an entity while an edge represents an interaction between two entities. A community arises in a&#xd;
network when two or more entities have common interests, e.g., related proteins, industrial sectors, groups&#xd;
of people, documents of a collection. There exist applications that model a community as a fixed graph&#xd;
H [98, 10, 119, 2, 142, 136]. Additionally, it is not expected that an entity of the network belongs to only&#xd;
one community; that is, communities tend to share their members.&#xd;
&#xd;
The community discovering or community detection problem consists on finding all communities in a&#xd;
given network. This problem has been extensively studied from a practical perspective [61, 137, 122, 116].&#xd;
However, we believe that this problem also brings many interesting theoretical questions. Thus in this&#xd;
thesis, we will address this problem using a more rigorous approach. To that end, we first introduce&#xd;
graph problems that we consider capture well the community discovering problem. These graph problems&#xd;
generalize the classical H-Packing problem [88] in two different ways.&#xd;
&#xd;
In the H-Packing with t-Overlap problem, the goal is to find in a given graph G (the network) at&#xd;
least k subgraphs (the communities) isomorphic to a member of a family of graphs H (the community&#xd;
models) such that each pair of subgraphs overlaps in at most t vertices (the shared members). On the&#xd;
other hand, in the H-Packing with t-Membership problem instead of limiting the pairwise overlap, each&#xd;
vertex of G is contained in at most t subgraphs of the solution. For both problems each member of H has&#xd;
at most r vertices and m edges. An instance of the H-Packing with t-Overlap and t-Membership problems&#xd;
corresponds to an instance of the H-Packing problem for t = 0 and t = 1, respectively. We also restrict&#xd;
the overlap between the edges of the subgraphs in the solution instead of the vertices (called H-Packing&#xd;
with t-Edge Overlap and t-Edge Membership problems).&#xd;
&#xd;
Given the closeness of the r-Set Packing problem [87] to the H-Packing problem, we also consider&#xd;
overlap in the problem of packing disjoint sets of size at most r. As usual for set packing problems, given&#xd;
a collection S drawn from a universe U, we seek a sub-collection S&amp;apos;⊆S consisting of at least k sets&#xd;
subject to certain disjointness restrictions. In the r-Set Packing with t-Membership, each element of U&#xd;
belongs to at most t sets of S&amp;apos; while in the r-Set Packing with t-Overlap each pair of sets in S&amp;apos; overlaps&#xd;
in at most t elements. For both problems, each set of S has at most r elements. We refer to all the&#xd;
problems introduced in this thesis simply as packing problems with overlap. Also, we group as the family&#xd;
of t-Overlap problems: H-Packing with t-Overlap, H-Packing with t-Edge Overlap, and r-Set Packing with&#xd;
t-Overlap. While we call the family of t-Membership problems: H-Packing with t-Membership, H-Packing&#xd;
with t-Edge Membership, and r-Set Packing with t-Membership.&#xd;
&#xd;
&#xd;
&#xd;
The classical H-Packing and r-Set Packing problems are NP-complete [87, 88]. We will show in this&#xd;
thesis that allowing overlap in a packing does not make the problems &amp;quot;easier&amp;quot;. More precisely, we show&#xd;
that the H-Packing with t-Membership and the r-Set Packing with t-Membership are NP-complete when&#xd;
H = {H&amp;apos;} and H&amp;apos; is an arbitrary connected graph with at least three vertices and r≥3, respectively.&#xd;
&#xd;
Parameterized complexity, introduced by Downey and Fellows [44], is an exciting and interesting approach&#xd;
to deal with NP-complete problems. The underlying idea of this approach is to isolate some aspects&#xd;
or parts of the input (known as the parameters) to investigate whether these parameters make the problem&#xd;
tractable or intractable. The main goal of this thesis is to study the parameterized complexity of our packing&#xd;
problems with overlap. We set up as a parameter k the size of the solution (number of communities),&#xd;
and we consider as fixed-constants r, m and t.&#xd;
&#xd;
We show that our problems admit polynomial kernels via two types of techniques: polynomial parametric&#xd;
transformations (PPTs) [16] and classical reduction algorithms [43]. PPTs are mainly used to show&#xd;
lower bounds and as far as we know they have not been used as extensively to obtain kernel results as&#xd;
classical kernelization techniques [96, 42]. Thus, we believe that employing PPTs is a promising approach&#xd;
to obtain kernel reductions for other problems as well. On the other hand, with non-trivial generalizations&#xd;
of kernelization algorithms for the classical H-Packing problem [114], we are able to improve our kernel&#xd;
sizes obtained via PPTs. These improved kernel sizes are equivalent to the kernel sizes for the disjoint&#xd;
version when t = 0 and t = 1 for the t-Overlap and t-Membership problems, respectively.&#xd;
&#xd;
We also obtain fixed-parameter algorithms for our packing problems with overlap (other than running&#xd;
brute force on the kernel). Our algorithms combine a search tree and a greedy localization technique and&#xd;
generalize a fixed-parameter algorithm for the problem of packing disjoint triangles [54]. In addition, we&#xd;
obtain faster FPT-algorithms by transforming our overlapping problems into an instance of the disjoint&#xd;
version of our problems.&#xd;
&#xd;
Finally, we introduce the Π-Packing with α()-Overlap problem to allow for more complex overlap&#xd;
constraints than the ones considered by the t-Overlap and t-Membership problems and also to include&#xd;
more general communities definitions. This problem seeks at least k induced subgraphs in a graph G&#xd;
subject to: each subgraph has at most r vertices and obeys a property Π (a community definition) and for&#xd;
any pair of subgraphs Hi,Hj, with i≠j, we have that α(Hi,Hj) = 0 holds (an overlap constraint).&#xd;
&#xd;
We show that the Π-Packing with α()-Overlap problem is fixed-parameter tractable provided that Π&#xd;
is computable in polynomial time in n and α() obeys some natural conditions. Motivated by practical&#xd;
applications we give several examples of α() functions which meet those conditions.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">fixed-parameter algorithms</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">kernelization</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">set packing</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">graph packing</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">overlapping communities</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Generalized Set and Graph Packing Problems</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Doctoral Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">David R. Cheriton School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="discipline" lang="en">Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="grantor" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Doctor of Philosophy</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Lopez Ortiz, Alejandro</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="affiliation1" lang="en">Faculty of Mathematics</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="city" lang="en">Waterloo</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="country" lang="en">Canada</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="province" lang="en">Ontario</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>