# Celebrity Cliques In Optimal Time

A party $$P$$ is a set of distinct people with a relation $$\text{knows}$$.

A non-empty subset $$C$$ of $$P$$ is a celebrity clique if everyone in the clique is known by everyone in the party, but the members of the clique only know each other. Formally,

$\forall x \in P, y \in C :: x \text{ knows } y \wedge (y \text{ knows } x \implies x \in C).$

You wish to design an algorithm which takes in the number of people ($$n$$), and the matrix that describes the $$\text{knows}$$ relation and determines if there is a celebrity clique in the party.

Which of the following is the sharpest lower bound?

×