Densesubgraph

Densesubgraph (often written as “dense subgraph”) refers to a subgraph with a high edge density relative to its size. In an undirected graph G=(V,E), a subgraph H=(V',E') with V'⊆V and E'⊆E is considered dense if the ratio of edges to vertices is large. Density is commonly defined as either |E'|/|V'| or as the average degree 2|E'|/|V'|; the two definitions differ by a constant factor.

The densest subgraph problem asks to find a nonempty subgraph that maximizes density. For undirected graphs, this problem can be solved exactly in polynomial time via a maximum-flow formulation, a result attributed to Goldberg. This makes the problem tractable in many practical settings, unlike several related optimization problems on graphs.

Related variants include the densest k-subgraph problem (DkS), which seeks a subgraph with exactly k vertices containing the maximum number of edges. DkS is NP-hard and is hard to approximate in general. In contrast, the standard densest subgraph problem admits efficient algorithms; Charikar (2000) proposed a simple greedy algorithm that yields a 2-approximation, and there are also approaches based on linear programming and parametric flow.

Applications of dense subgraph methods appear in social network analysis, bioinformatics, and data mining, where identifying cohesive, highly connected groups is valuable. Extensions handle weighted graphs, directed graphs, and constraints such as fixed or bounded subgraph size, minimum density requirements, or vertex weights.