## Computing role assignments of chordal graphs

*Pim van 't Hof, Daniël Paulusma and Johan M.M. van Rooij*

*Theoretical Computer Science*, vol. 411, no. 40-42, pp. 3601-3613, 2010.

[__DOI__]
[__Preprint__]

A preliminary version of this paper appeared in the proceedings of FCT 2009,
the 17th International Symposium on Fundamentals of Computation Theory
(held on September 2-4, 2009 in Wrocław, Poland),
*Lecture Notes in Computer Science*, vol. 5699, pp. 193-204.

[__DOI__]

### Abstract:

In social network theory, a simple graph *G* is called *k*-role assignable if there is a surjective mapping that assigns a number from {1,...,*k*}, called a role, to each vertex of *G* such that any two vertices with the same role have the same sets of roles assigned to their neighbors. The decision problem whether such a mapping exists is called the *k*-Role Assignment problem. This problem is known to be NP-complete for any fixed *k* ≥ 2. In this paper, we classify the computational complexity of the *k*-Role Assignment problem for the class of chordal graphs. We show that for this class the problem can be solved in linear time for *k = 2*, but remains NP-complete for any *k* ≥ 3. This generalizes earlier results by Sheng and answers her open problem.