Propose an algorithm to find a "celebrity"

Question

A celebrity is a person that everyone knows, but he doesn't know anyone.

If we think of a group of people as a graph, where if there is an arrow from $A$ to $B$ that means "$A$ knows $B$", then a celebrity is a vertex of the graph that everyone is pointing to him, but he points to no one. Meaning if $C$ is a celebrity in a group of $n$ people:

$Deg_{in}(C)=n-1$, $Deg_{out}(C)=0$

This diagram shows it more clearly:

here $C$ is a celebrity. Obviously there can't be more than $1$ celebrity in a group of $n$ people, because if $C$ is a celebrity, then he does not point to anyone, specifically he does not point to $D$, so $D$ is not a celebrity because not everyone knows him ($C$ doesn't).

Propose an efficient algorithm, that runs in minimal steps, to find the celebrity (the star) in a graph with $n$ vertices.

The best solution I came up with is run through all the vertices and check if the current vertex is a celebrity. Checking if a vertex is a celebrity can be done in $\Theta(1)$, but we run through (potentially) all the vertices, so overall it's $\Theta(n)$ which is pretty bad.

I'm sure there is a better way, since suppose we started at vertex $A$ and it doesn't point to $B$. Then we don't need to check $B$ now. For sure it's not a celebrity.

Answer 1

Whenever you are at a vertex $X$ and $X$ is not a celebrity, you can remove from the search, not only $X$ but all vertices that know (point to) $X$. None of these are celebrities either. Therefore you only have to move to vertices that $X$ points to.

The best one can do in this problem is $O(n)$. Suppose that we have a $K_{n-1}$ where all edges point in both directions and a vertex $c$, the celebrity, to which all the vertices in the $K_{n-1}$ point to.

Given an algorithm $A$ that finds $C$ if $v_1\in V(K_{n-1})$ is the vertex that makes $A$ do the longest search, then $v_1\neq C$. By the symmetry of the graph this vertex is indistinguishable from all other vertices of the $K_{n-1}$. So, the algorithm gives the worst search for all vertices in the $K_{n-1}$. With the information in the vertex $v_1$ is not possible to detect where is $C$. Therefore in the worst search for $A$ it will move to some vertex $v_2$ of the $K_{n-1}$. We can remove the $v_1$ and its edges from the graph and we are in the same situation but with a graph with a $K_{n-2}$. By induction the worst search is $O(n-1)$ in that graph.

Answer 2

Initialize your set of possible celebrities to the whole set of vertices.

At each iteration, select a vertex from the set of possible celebrities.

If it is a celebrity, you are done.

If not, the list of celebrities is modified so that only people that your choice knows remain on the list. (The celebrity must be known by your choice.)

Repeat

The algorithm runs very quickly if your first (or an early) choice has low "out-degree."

Answer 3

Why not combine both the solutions we have? Start with a list of possible celebrity candidates $L$. At each step select a vertex $v$ from $L$ and check if he is celebrity, if not delete all the people from $L$ that $v$ does not know and all the people that know $v$. This algorithm seems rather good because it solves both the examples that are troublesome for the other two proposed algorithms in one step.