On finding dense subgraphs

Samir Khuller*, Barna Saha

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

112 Scopus citations

Abstract

Given an undirected graph G=(V,E), the density of a subgraph on vertex set S is defined as d(S) = |E(S)|/|S| , , where E(S) is the set of edges in the subgraph induced by nodes in S. Finding subgraphs of maximum density is a very well studied problem. One can also generalize this notion to directed graphs. For a directed graph one notion of density given by Kannan and Vinay [12] is as follows: given subsets S and T of vertices, the density of the subgraph is d(S, T) = √E(S,T)|/|S||T|, where E(S,T) is the set of edges going from S to T. Without any size constraints, a subgraph of maximum density can be found in polynomial time. When we require the subgraph to have a specified size, the problem of finding a maximum density subgraph becomes NP-hard. In this paper we focus on developing fast polynomial time algorithms for several variations of dense subgraph problems for both directed and undirected graphs. When there is no size bound, we extend the flow based technique for obtaining a densest subgraph in directed graphs and also give a linear time 2-approximation algorithm for it. When a size lower bound is specified for both directed and undirected cases, we show that the problem is NP-complete and give fast algorithms to find subgraphs within a factor 2 of the optimum density. We also show that solving the densest subgraph problem with an upper bound on size is as hard as solving the problem with an exact size constraint, within a constant factor.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 36th International Colloquium, ICALP 2009, Proceedings
Pages597-608
Number of pages12
EditionPART 1
DOIs
StatePublished - Nov 12 2009
Event36th International Colloquium on Automata, Languages and Programming, ICALP 2009 - Rhodes, Greece
Duration: Jul 5 2009Jul 12 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume5555 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference36th International Colloquium on Automata, Languages and Programming, ICALP 2009
CountryGreece
CityRhodes
Period7/5/097/12/09

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On finding dense subgraphs'. Together they form a unique fingerprint.

Cite this