# In Search of the Densest Subgraph
## 3 Measures of Graph Density and Associated Results
### NP-Hard Density Measures and Related Results  
#### 3.2.1 Maximum Clique  
The archetypal example of a dense subgraph is a _clique_, i.e. a complete subgraph. Of course, we do not just look for _any_ clique, since that would be trivial (a single edge is already a clique). Normally, we want to find a _maximum clique_, that is, the one with the largest possible number of vertices. This task, however, is one of the best known and earliest **NP**-complete problems (see, e.g. [PERSON] and [PERSON] [18]). Specifically, the following problem is **NP**-complete:  
* Clique _Input:_ Graph \(G\), positive integer \(k\) _Question:_ Does \(G\) have a clique of size at least \(k\)? The above is the _decision version_ of the problem. The corresponding _optimization version_ or _search problem_ is **NP**-hard:  
* Maxclique _Input:_ Graph \(G\) _Task:_ Find a maximum clique in \(G\). At this point, one may wonder: If we know the answer to the decision problem for the input graph \(G\), could it make the optimization/search easier? The answer is no (see, e.g., [PERSON] [19]):  
**Theorem 2**. : _If \(\textbf{P}\
eq\textbf{NP}\), then there is no polynomial-time algorithm to find a clique of size \(k\) in a graph \(G\), even if it is guaranteed that \(G\) has a clique of size \(k\)._  
On the other hand, if a subroutine (often referred to as _oracle_) is available that can solve the decision problem for _any_ graph, not just for the input at hand, then calling it only polynomially many times is already enough to solve the optimization/search problem efficiently, assuming that an oracle call is counted as a single step. The reason is that one can reduce a large instance to a smaller one, and repeating it recursively step by step allows recovering the nodes of a maximum clique. This kind of approach applies to every **NP**-complete problem, and it is called _self-reducibility_[18]. Metaphorically speaking, if we know that the haystack contains a needle, but this fact alone does not make it easier to find the needle. If, however, we can decide for _any_ haystack whether it contains a needle, that already allows finding the needle efficiently. Faster Exponential-time Algorithms  
Even though no polynomial-time algorithm is expected to exist to find a maximum clique, this does not mean that the best possibility is exhaustive search. Naive exhaustive search of all node subsets in a graph with \(n\) nodes would take examining \(2^{n}\) subsets in the worst case. However, significantly faster, yet still exponential-time, algorithms exist. [PERSON] [20] published an algorithm that runs in \(O(1.2108^{n})\) time. It was further improved by [PERSON] in a technical report [PERSON] [21], to \(O(1.1888^{n})\) time, which is apparently the fastest to date. Note that there can be a dramatic difference between \(2^{n}\) and \(1.1888^{n}\). For example, in a small graph with only \(n=20\), we can already see a big difference: \(2^{n}\) is more than a million, while \(1.1888^{n}\) is less than 32. Approximation  
Since there is no realistic chance to always find a truly maximum clique in any input graph faster than exponential time, it is natural to look for approximations. However, it is far from easy. A general result is due to [PERSON] and [PERSON] [22]; they provided a polynomial-time algorithm that guarantees an approximation ratio of \(O(n/\log^{2}n)\) for any graph of \(n\) vertices. The approximation ratio was later improved by [PERSON] [23] by a factor of \(O((\log\log n)^{2}/\log n)\) to \(O(n(\log\log n)^{2}/\log^{3}n)\). To put the results in context, note that an \(O(n)\) approximation is trivial, as a single node already achieves it. The above factors are slightly better than \(O(n)\), but not much. They cannot even share off an \(O(n^{\epsilon})\) factor for any \(\epsilon>0\), despite their rather sophisticated methods.