TY - GEN

T1 - On finding dense subgraphs

AU - Khuller, Samir

AU - Saha, Barna

PY - 2009/11/12

Y1 - 2009/11/12

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

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

UR - http://www.scopus.com/inward/record.url?scp=70449135268&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70449135268&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-02927-1_50

DO - 10.1007/978-3-642-02927-1_50

M3 - Conference contribution

AN - SCOPUS:70449135268

SN - 3642029264

SN - 9783642029264

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 597

EP - 608

BT - Automata, Languages and Programming - 36th International Colloquium, ICALP 2009, Proceedings

T2 - 36th International Colloquium on Automata, Languages and Programming, ICALP 2009

Y2 - 5 July 2009 through 12 July 2009

ER -