Computing role assignments of chordal graphs
Pim van 't Hof, Daniel Paulusma and Johan M.M. van Rooij
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>1. 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 becomes polynomially solvable for k=2, but
remains NP-complete for any k>2. This generalizes results of Sheng and
answers his open problem.