# 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
Inapproximability  
The fact that decades of research could not turn up a polynomial-time approximation algorithm for Maxclique with approximation ratio \(O(n^{1-\epsilon})\) for any \(\epsilon>0\), no matter how small, seems to indicate that such an algorithm perhaps does not exist at all, under some plausible complexity theoretic assumptions. After a number of gradually improving earlier results, eventually it was proved by [PERSON] [24] that this is indeed the case, and the only assumption needed is \(\mathbf{P}\
eq\mathbf{NP}\). Specifically, he proved that, for any \(\epsilon>0\), finding an \(O(n^{1-\epsilon})\) approximation of the maximum clique in an \(n\)-vertex graph is \(\mathbf{NP}\)-hard. The above result means that Maxclique indeed behaves very rigidly regarding approximation: while an \(O(n)\) approximation is trivial, anything of the form \(O(n^{\alpha})\) with \(\alpha<1\) is virtually impossible, i.e., no \(O(n^{1-\epsilon})\) approximation exists for any \(\epsilon>0\), unless \(\mathbf{P}=\mathbf{NP}\). While the above results show that in general graphs there is no chance to efficiently find a maximum clique, or even a reasonably good approximation, it does not mean that one cannot achieve success when the input is restricted to some special graph class. Examples of well-known classes with polynomial-time Maxclique algorithms are perfect graphs, planar graphs, unit disc graphs (with a given geometric representation), various types of intersection graphs, etc. If one also includes less well known classes, then actually there are hundreds of classes, for which Maxclique can be solved in polynomial time (see [25]). While finding a maximum clique is hard, listing _all_ inclusion-wise maximal cliques, which, of course, include all maximum (notice the difference in word usage: maximum refers to the largest, while maximal refers to inclusion, meaning that it cannot be extended into a larger clique, but it may not itself be largest) cliques also can be done in polynomial time. This may first sound contradictory. However, there are usually exponentially many maximal cliques, and they all have to be listed in the output, which allows us exponential running time in terms of the graph size. To have some efficiency, we expect that, on average, the algorithm does only a polynomial amount of work per output configuration. However, regarding such enumeration algorithms, a stricter quantity that is often considered as a measure of efficiency is called _delay_. We say that an enumeration algorithm has _polynomial delay_, if it generates the configurations (in our case the maximal cliques), one after the other in some order, in such a way that the delay until the first output, the delay between any two consecutive outputs, and the delay until it stops after the last output are bounded by a polynomial in the input size (the graph size). Despite the hardness of Maxclique, listing all maximal cliques with polynomial delay is possible. Such an algorithm was developed by [PERSON], [PERSON], [PERSON], and [PERSON] [26]:  
There is an algorithm enumerating all maximal cliques of a graph with \(O(n^{3})\) delay, using \(O(n+m)\) space, where \(n\) is the number of vertices and \(m\) is the number of edges. What if we want to list all maximal cliques in some specific order, not just any order? For certain orders, such as lexicographic order, this is also possible with polynomial delay, but needs further tricks. [PERSON], [PERSON], and [PERSON] [27] proved the following result:  
There is an algorithm enumerating all maximal cliques of an \(n\)-vertex graph in lexicographic order with \(O(n^{3})\) delay. They also proved that the same is likely impossible for some other orders:  
If \(\mathbf{P}\
eq\mathbf{NP}\), then there is no algorithm that generates for any given graph all maximal cliques in inverse lexicographic order with polynomial delay.