# In Search of the Densest Subgraph
## 3 Measures of Graph Density and Associated Results
### NP-Hard Density Measures and Related Results
#### 3.2.3 Flexes  
A graph that is close to a clique in the sense that only a few edges are missing at every vertex to connect it to all others, is called a _plex_. The formal definition is this:  
A \(k\)-plex in a graph \(G\) is a subgraph \(S\), such that for every \(x\in V(S)\) it holds that \(d_{S}(x)\geq|V(S)|-k\). With this definition, a clique is a 1-plex, since every node has degree \(|V(S)|-1\). For \(k>1\), we allow that some edges are missing from the clique. However, for moderate values of \(k\), not too many edges are missing, so the graph is close to a clique. As plexes approximate cliques rather closely, it is not surprising that finding them is hard. It is expressed by the following theorem (see [PERSON] [19]):  
For any positive integer \(k\), it is \(\mathbf{NP}\)-complete to decide whether a given graph contains a \(k\)-plex with at least a given number of nodes. An interesting feature of \(k\)-plexes is that one can prove a relationship between the value of \(k\), and the _diameter_ of the graph. The diameter \(diam(G)\) of a connected graph \(G\) is the largest hop-distance that can occur between any two nodes. One can prove the following (see [PERSON] [19]):  
Let \(G\) be a connected \(n\)-vertex \(k\)-plex, with \(1\leq k\leq n\). Then,\(k<\frac{n+2}{2}\) implies \(diam(G)\leq 2\). \(k\geq\frac{n+2}{2}\) implies \(diam(G)\leq 2k-n+2\). Density Relative to A Clique  
Another way of measuring the density is to express what fraction of all possible edges are contained in a graph, i.e., how close it is to a clique in terms of the number of edges. Definition 6: Let \(G\) be an \(n\)-vertex graph with \(m\) edges, and let \(0\leq\eta\leq 1\) be a real number. Then, \(G\) is said to be \(\eta\)-dense if  
\[\frac{m}{n(n-1)/2}\geq\eta.\]  
Not surprisingly, it is **NP**-complete to decide whether an \(\eta\)-dense subgraph of a given size exists in an input graph. This follows from the results of the next subsection as a special case, due to the fact that an \(\eta\)-dense subgraph of a given size is a subgraph of a given size having at least a given number of edges. A notable feature of \(\eta\)-density is that it is inherited by subgraphs, in a sense similar to the clique property. However, the property is not as strong as in the case of cliques: if in a clique we delete any vertex, then we get a clique again. In an \(\eta\)-dense graph, one can only prove that there is a vertex whose deletion preserves the \(\eta\)-density, but this may not hold for all vertices. Note that many other density measures do not have even this weaker inheritance property. Specifically, one can prove (see [PERSON] [19]):  
Theorem 8: _Let \(0\leq\eta\leq 1\) be a real number. An \(\eta\)-dense \(n\)-vertex graph always contains an \(\eta\)-dense \((n-1)\)-vertex subgraph._  
Constrained size Subgraphs with Maximum Number of Edges  
Another reasonable concept of a densest subgraph, approximating a clique, is expressed by the following problem: a number \(k\) as input and we look for a \(k\)-vertex subgraph with the maximum number of edges. As it contains Maxclique as a special case, it is **NP**-hard. Interestingly, as proved by [PERSON], [PERSON] and [PERSON] [28], it remains **NP**-hard even if we are satisfied with a subgraph that has only \(\Theta(k^{1+\epsilon})\) edges, where \(0<\epsilon<1\) is any fixed constant. On the other hand, it can be approximated in polynomial time within approximation ratio \(n^{1/4+\epsilon}\), for every \(\epsilon>0\), in time \(n^{O(1/\epsilon)}\), as proved by [PERSON] et al. [29]. For special graph classes, stronger results are available. For example, polynomial-time constant factor approximations have been developed for many intersection graph classes (see [PERSON], [PERSON], and [PERSON] [30]). If the whole input graph is dense, which means that the minimum degree is at least \(\delta n\) for some constant \(\delta>0\), then the problem has a Polynomial-Time Approximation Scheme (PTAS), as proved by [PERSON], [PERSON], and [PERSON] [31].