Celebrity Cliques In Optimal Time

Computer Science Level 4

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?

Inspired by Richard Bird's Pearls of Functional Programming

Problem Loading...

Note Loading...

Set Loading...