My Constraint Programming Blog

This problem is from Uwe Hoffmann Finding celebrities at a party (PDF):

Problem: Given a list of people at a party and for each person the list of people they know at the party, we want to find the celebrities at the party. A celebrity is a person that everybody at the party knows but that only knows other celebrities. At least one celebrity is present at the party.

(This paper contains an implementation of the problem in Scala.)

Note: The original of this problem is Richard Bird and Sharon Curtis: "Functional pearls: Finding celebrities: A lesson in functional programming" (J. Funct. Program., 16(1):13–20, 2006), but I (nor Hoffmann) have not been able to access this paper. Update: I have now got hold of this paper. Thank you SW!

The example in Hoffmann's paper is to find of who are the celebrity/celebrities in this party graph:

Adam  knows {Dan,Alice,Peter,Eva},
Dan   knows {Adam,Alice,Peter},
Eva   knows {Alice,Peter},
Alice knows {Peter},
Peter knows {Alice}

Solution: the celebrities are Peter and Alice.

MiniZinc model

The MiniZinc model of this problem is finding_celebrities.mzn.

Following are some discussion of the two constraints

• All must knows a celebrity
• Celebrities only knows a celebrity

But first a comment how the party graph is represented.

Party graph

Here I have chosen to represent the party as an array of sets:

  Adam  (1) knows {Dan,Eva,Alice,Peter}  {2,3,4,5}
  Dan   (2) knows {Adam,Alice,Peter}     {1,4,5}
  Eva   (3) knows {Alice,Peter}          {4,5}
  Alice (4) knows {Peter}                {5}
  Peter (5) knows {Alice}                {4}

This is coded in MiniZinc as:

party = [
          {2,3,4,5}, % 1, Adam
          {1,4,5},   % 2, Dan 
          {4,5},     % 3, Eva
          {5},       % 4, Alice
          {4}        % 5, Peter
         ];

This corresponds to the following incidence matrix, which is calculated in the model. For simplifying the calculations, we assume that a person know him/herself (this is also handled in the model).

% 1 2 3 4 5
  1,1,1,1,1, % 1
  1,1,0,1,1, % 2
  0,0,1,1,1, % 3
  0,0,0,1,1, % 4
  0,0,0,1,1  % 5

This conversion from incidence sets (party) to incidence matrix (graph) is done by the set2matrix predicate:

predicate set2matrix(array[int] of var set of int: s,
                     array[int,int] of var int: mat) =
     forall(i in index_set(s)) ( graph[i,i] = 1)
     /\
     forall(i,j in index_set(s) where i != j) (
      j in party[i] <-> graph[i,j] = 1
    )

All must know a celebrity

I started this model by consider the celebrities as a clique, and therefore using the constraint clique (which is still included in the model). However, is not enough to identify the clique since there may be other cliques but are not celebrities. In the above example there is another clique: {Dan,Adam}.

In fact, the clique constraint is not needed at all (and it actually makes the model slower). Instead we can just look for person(s) that everybody knows, i.e. where there are all 1's in the column of a celebrity in the party graph matrix (graph in the model). This is covered by the constraint:

forall(i in 1..n) (
   (i in celebrities -> sum([graph[j,i] |j in 1..n]) = n)
)  

This is a necessary condition but not sufficient for identifying celebrities.

Celebrities only know each other

We must also add the constraint that all people in the celebrity clique don't know anyone outside this clique. This is handled by the constraint the all celebrities must knows the same amount of persons, i.e. the size (cardinality) of the clique:

forall(i in 1..n) (
   i in celebrities -> sum([graph[i,j] | j in 1..n]) = num_celebrities
)

As noted above, a person is assumed to know him/herself.

Running the model

If we run the MiniZinc model finding_celebrities.mzn we found the following solution:

celebrities = 4..5;
num_celebrities = 2;

which means that the celebrities are {4,5}, i.e. {Alice, Peter}.

Another, slightly different party

We now change the party matrix slightly by assuming that Alice (4) also know Adam (1), i.e. the following incidence matrix:

 % 1 2 3 4 5
   1,1,1,1,1, % 1
   1,1,0,1,1, % 2
   0,0,1,1,1, % 3
   1,0,0,1,1, % 4
   0,0,0,1,1  % 5
]);

This makes Alice a non celebrity since she knows the non celebrity Adam, and this in turn also makes Peter a non celebrity since he knows the non celebrity Alice. In short, in this party there are no celebrities.

The model also contains a somewhat larger party graph with 10 persons.

Update about 8 hours later There is now a version which uses just set constraints, i.e. no conversion to an incidence matrix: finding_celebrities2.mzn. The constraint sections is now:

constraint
  num_celebrities >= 1

  /\ % all persons know the celebrities,
     % and the celebrities only know celebrities
  forall(i in 1..n) (
     (i in celebrities -> 
             forall(j in 1..n where j != i) (i in party[j]))
     /\
     (i in celebrities -> 
             card(party[i]) = num_celebrities-1)
  )

I have kept the same representation of the party (the array of sets of who knows who) as the earlier model which means that a person is now not assuming to know him/herself. The code reflects this change by using where j != i and num_celebrities-1.