How hard is it to determine if a graph has a 2-role assignment?

Role assignments, introduced by Everett and Borgatti [2], who called them role colorings, formalize the idea, arising in the theory of social networks, that individuals of the same social role will relate in the same way to the individuals playing counterpart roles. If G is a graph, a k-role assignment is a function r mapping the vertex set onto the set of integers {1,2,. . . , k} so that if r(x) = r(y) then the sets of roles assigned to the neighbors of x and y are the same. We ask how hard it is to determine if a graph has a 2-role assignment and show that recognizing if a graph has a 2-role assignment is NP-complete.