Among n
persons,a "celebrity" is defined as someone
who is known by everyone but does not know anyone. The
problem is to identify the celebrity, if one exists, by asking the
question only of the form, "Excuse me, do you know the person
over there?" (The assumption is that all the answers are correct,
and even that celebrity will also answer.)
The goal is to minimize the number of questions.
Is there a solution of the order less than the obvious O(n^2)
here?
Using the analysis of the celebrity problem here
Brute-force solution. The graph has at most
n(n-1)
edges, and we can compute it by asking a question for each potential edge. At this point, we can check whether a vertex is a sink by computing its indegree and its outdegree. This brute-force solution asksn(n-1)
questions. Next we show how to to do this with at most3(n-1)
questions and linear place.An elegant solution. Our algorithm consists of two phases: in the elimination phase, we eliminate all but one person from being the celebrity; in the verification phase we check whether this one remaining person is indeed a celebrity. The elimination phase maintains a list of possible celebrities. Initially it contains all
n
people. In each iteration, we delete one person from the list. We exploit the following key observation: if person1
knows person2
, then person1
is not a celebrity; if person1
does not know person2
, then person2
is not a celebrity. Thus, by asking person1
if he knows person2
, we can eliminate either person1
or person2
from the list of possible celebrities. We can use this idea repeatedly to eliminate all people but one, say personp
. We now verify by brute force whetherp
is a celebrity: for every other personi
, we ask personp
whether he knows personi
, and we ask personsi
whether they know personp
. If personp
always answers no, and the other people always answer yes, the we declare personp
as the celebrity. Otherwise, we conclude there is no celebrity in this group.