A clique problem equivalent to graph isomorphism
Dexter C. Kozen · ACM SIGACT News · 1978
A class of graphs called M-graphs is defined. It is shown thati) the problem of determining whether a given M-graph of order n 2 has a clique of order n is logspace equivalent to graph isomorphism, andii) for any fixed but arbitrarily small e, the problem of determining whether a given M-graph of order n 2 has a clique of order (1-e)n is NP complete.