Back to search

University of Waterloo

The Complexity of Finding Dense Subgraphs in Graphs with Large Cliques

Abstract

dc:description.abstract

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. 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. 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. 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).

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2021

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Seth, Cameron
Advisor dc:contributor.advisor
  • Blais, Eric

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/17249

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Seth, Cameron. The Complexity of Finding Dense Subgraphs in Graphs with Large Cliques. University of Waterloo, 2021. http://hdl.handle.net/10012/17249