# In Search of the Densest Subgraph
## 3 Measures of Graph Density and Associated Results
### Polynomial-Time Solvable Cases  
#### 3.1.1 Edge Density: Subgraph with Maximum Average Degree  
A very natural first measure of density is the number of edges divided by the number of nodes in the subgraph, since more edges on the same number of nodes provide an intuitively denser, more cohesive subgraph. Denoting this density by \(\rho_{1}\), we get  
\[\rho_{1}(S)=\frac{|E(S)|}{|V(S)|}\,.\]  
This is sometimes called _edge density_, or just density, for short. Observe that \(|E(S)|\) is precisely half of the sum of the degrees in the subgraph \(S\), since each edge contributes 2 to the sum of degrees. Therefore, we can write  
\[\rho_{1}(S)=\frac{1}{2}\frac{\sum_{x\in V(S)}d_{S}(x)}{|V(S)|}=\frac{1}{2} \,\overline{d}(S),\]  
that is, \(\rho_{1}(S)\) is half of the average vertex degree in \(S\). Thus, finding a subgraph \(S\) that maximizes the density \(\rho_{1}(S)\) is equivalent to finding a subgraph with maximum average degree.  
This task, while not at all trivial, can be solved in polynomial time, in several different ways. A network flow based solution was already published in 1982 by [PERSON] and [PERSON] [3]. The running time was improved by [PERSON], [PERSON] and [PERSON] [4] in 1989, keeping the network flow based approach. [PERSON] [5] showed in 2000 that the density value \(\rho_{1}(S)\) of the densest subgraph \(S\) is equal to the optimal solution of the following simple linear program: assign a variable \(x_{ij}\) to every edge \((i,j)\) and a variable \(y_{i}\) to every node \(i\), and consider the linear program  
\[\max\sum_{i,j}x_{ij}\]  
Subject to  
\[\forall i,j:\ x_{ij} \leq y_{i}\] \[\forall i,j:\ x_{ij} \leq y_{j}\] \[\sum_{i}y_{i} \leq 1\] \[\forall i,j:\ x_{ij},y_{i} \geq 0.\]  
From this not only a polynomial-time solution can be derived, but it also allows a generalization to directed graphs. Furthermore, it also gives rise to a very simple 2-approximation algorithm. Specifically, the approximation algorithm starts with \(S_{0}=G\), and then removes a vertex \(x\in V(S_{0})\) for which \(d_{S_{0}}(x)\) is minimum, i.e., a minimum degree vertex from \(S_{0}\), to obtain a new (smaller) subgraph \(S_{1}\). Then, again, a minimum degree vertex is removed from \(S_{1}\), to obtain \(S_{2}\), and so on, until we arrive at an empty graph, after at most \(n=|V(G)|\) iterations. Then, from the generated graph sequence \(S_{0},S_{1},S_{2},\ldots\), we select the one for which \(\rho_{1}(S_{i})\) is the largest. [PERSON] [5] proved that this surprisingly simple algorithm guarantees an approximation ratio not worse than 2, that is, it finds a subgraph with at least half of the optimum density.  
Another polynomial-time algorithm was given by [PERSON] and [PERSON] [6] in 2004. In 2008, [PERSON] [7] provided an algorithm that reduces the problem to bipartite matching, also allowing generalizations to more complex density concepts (see Section 3.1.4). Apparently, the fastest asymptotic running time to date for finding the exact optimum is achieved by the parametric maximum flow based algorithm of [PERSON], [PERSON] and [PERSON] [4], which runs in time \(O(nm\log(n^{2}/m))\) on a graph of \(n\) vertices and \(m\) edges.