# In Search of the Densest Subgraph
## 3 Measures of Graph Density and Associated Results
### Polynomial-Time Solvable Cases
#### 3.1.4 Subgraph with Maximum F-Density  
A further generalization was introduced by [PERSON] [7]. For notational convenience, if \(\mathbf{F}\) is a set of graphs, then we say that a graph \(G\) is an \(\mathbf{F}\)-graph if \(G\in\mathbf{F}\). **Definition 2**. : _Let \(\mathbf{F}\) be a fixed finite set of graphs. The \(\mathbf{F}\)-density of a graph \(S\) is defined by_  
\[\rho(S,\mathbf{F})=\frac{M(S,\mathbf{F})}{|V(S)|}\]  
_where \(M(S,\mathbf{F})\) denotes the number of \(\mathbf{F}\)-graphs in \(S\)._  
Let us illustrate the concept by some simple examples. **Example 1**. : _If \(\mathbf{F}\) consists of only one graph, which is a single edge, then we get back the definition of the edge-density of Section 3.1.1:_  
\[\rho_{1}(S)=\frac{|E(S)|}{|V(S)|}=\frac{1}{2}\,\frac{\sum_{x}d_{S}(x)}{|V(S)|}\,.\]  
**Example 2**. : _If \(\mathbf{F}\) consists of a triangle (a complete graph on three vertices), then we obtain the triangle-density: the number of triangles divided by the number of vertices, which we have already encountered in Section 3.1.3. Similarly, if \(\mathbf{F}\) consists of a k-clique, then we get back the k-clique density of Section 3.1.3._  
**Example 3**. : _Let \(\mathbf{F}\) consist of a single graph that is a path of length 2 (on three vertices). Then, each occurrence of such a path in a graph can be described by the position of the middle vertex of the path and the two edges adjacent to it. It is easy to see that the number of such paths with middle vertex \(x\in V(S)\) is \(\binom{d_{S}(x)}{2}\), and if two paths have different middle vertices then they cannot coincide. Therefore, the resulting density measure is_  
\[\rho_{2}(G)=\frac{1}{|V(S)|}\sum_{x}\binom{d_{S}(x)}{2}.\]  
**Example 4**. : _Let us combine Examples 1 and 3, and put now two graphs in \(\mathbf{F}\): a single edge and a path of length 2. It yields the density_  
\[\rho_{3}(S)=\frac{\sum_{x}\binom{d_{S}(x)}{2}+\frac{1}{2}\sum_{x}d_{S}(x)}{|V( S)|}=\frac{1}{2}\,\frac{\sum_{x}d_{S}^{2}(x)}{|V(S)|}\,.\]  
_That is, instead of the average degree, we aim here at maximizing the average of the squared degrees. The effect is that larger degrees have bigger contribution, so the subgraph will be pulled towards larger degrees._  
A key result of the paper Farago [7] is that for any fixed finite set \(\mathbf{F}\) of graphs, and for any input graph \(G\), a subgraph with maximum \(\mathbf{F}\)-density can be found in polynomial time. This allows efficiently finding maximally dense subgraphs with respect to new density measures. For example, Examples 3 and 4 provide densities that differ non-trivially from all cases covered by the previous sections. On the other hand, if \(\mathbf{F}\) is not fixed, then the problem becomes \(\mathbf{NP}\)-hard. Let us mention incidentally that the optimization of the \(\mathbf{F}\)-density in [7] is based on another graph optimization problem that is called the maximization of the weighted _independence ratio_, which is quite interesting on its own. To explain it, let us introduce some notations. A subset of vertices is called _independent_ if there is no edge between any two of the nodes in the subset. Let \(\mathcal{F}(G)\) be the family of all nonempty independent sets in the graph \(G\). For a set \(A\) of vertices, \(\Gamma(A)\) denotes the set of neighbors of \(A\), that is,  
\[\Gamma(A)=\{y|\ \exists x\in A:\ (x,y)\in E(G)\}.\]  
Assume that a positive integer weight function \(w\) is given on the nodes. The weight of a set \(A\) is denoted by \(w(A)\) and is defined as the sum of the weights of vertices in \(A\). **Definition 3** (Independence ratio). : _The independence ratio of an independent set \(A\in\mathcal{F}(G)\) with \(\Gamma(A)\
eq\emptyset\) is defined as_  
\[\gamma^{(w)}(A)=\frac{w(A)}{w(\Gamma(A))}.\]  
_If \(\Gamma(A)=\emptyset\), then we define \(\gamma^{(w)}(A)=\infty\)._  
We are looking for an independent set with _maximum independence ratio_.