<?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-22T18:05:33Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/17249" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/17249</identifier><datestamp>2025-03-26T23:35:55Z</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">Blais, Eric</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="c9277e8f-1693-468e-9123-2e4f4042a9f8" confidence="600">Seth, Cameron</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2021-08-25T16:14:56Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2021-08-25T16:14:56Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2021-08-25</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2021-08-15</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/17249</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">The GapDensest-k-Subgraph(d) problem (GapDkS(d)) is defined as follows: given a graph G and parameters k,d, distinguish between the case that G contains a k-clique, and the case that every k-subgraph of G has density at most d.&#xd;
&#xd;
GapDkS(d) is a natural relaxation of the standard Clique problem, which is known to be NP-complete. For d very close to 1, the GapDkS(d) problem is equivalent to the Clique problem, and when d is very close to 0 the GapDkS(d) problem can easily be solved in polynomial time. However, despite much work on both the algorithmic and hardness front, the exact k and d parameter values for which GapDkS(d) can be solved in polynomial time are still unknown. In particular, the best polynomial-time algorithms can solve GapDkS(d) when d is an inverse polynomial in the number of vertices n, but there have been no NP-hardness results beyond the trivial result.&#xd;
&#xd;
This thesis attempts to understand the GapDkS(d) problem better by studying the case when k is restricted to be linear in n (where n is the number of vertices in G). In particular, we survey the GapDkS(d) algorithms and hardness results that can be best applied to this restriction in an attempt to determine the threshold for when the problem becomes NP-hard. With some modifications to the algorithms and proofs, we produce algorithms and hardness results for the GapDkS(d) problem with k linear in n.&#xd;
&#xd;
In addition, we study the connection between GapDkS(d) and MaxClique, and show that despite having strong hardness results for MaxClique, reductions from MaxClique do not give strong hardness bounds for GapDkS(d).</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">approximation algorithms</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">NP Hardness</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">densest k-subgraph</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">The Complexity of Finding Dense Subgraphs in Graphs with Large Cliques</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master 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">Master of Mathematics</dim:field>
   <dim:field mdschema="uws-etd" element="embargo" qualifier="terms" lang="en">0</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Blais, Eric</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>