# On finding dense subgraphs

Samir Khuller*, Barna Saha

*Corresponding author for this work

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

173 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 language English (US) Automata, Languages and Programming - 36th International Colloquium, ICALP 2009, Proceedings 597-608 12 PART 1 https://doi.org/10.1007/978-3-642-02927-1_50 Published - 2009 36th International Colloquium on Automata, Languages and Programming, ICALP 2009 - Rhodes, GreeceDuration: Jul 5 2009 → Jul 12 2009

### Publication series

Name Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) PART 1 5555 LNCS 0302-9743 1611-3349

### Conference

Conference 36th International Colloquium on Automata, Languages and Programming, ICALP 2009 Greece Rhodes 7/5/09 → 7/12/09

## ASJC Scopus subject areas

• Theoretical Computer Science
• General Computer Science

## Fingerprint

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