Computing role assignments of chordal graphs

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


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 becomes polynomially solvable for k = 2, but remains NP-complete for any k ≥ 3. This generalizes results of Sheng and answers his open problem.
Original languageEnglish
Title of host publicationFundamentals of Computation Theory, 17th International Symposium, FCT 2009, Wroclaw, Poland, September 2-4, 2009. Proceedings
EditorsMiroslaw Kutylowski, Witold Charatonik, Maciej Gebala
Number of pages12
Publication statusPublished - 2009
Externally publishedYes
Event17th International Symposium on Fundamentals of Computation Theory, FCT 2009 - Wrocław, Poland
Duration: 2 Sept 20094 Sept 2009
Conference number: 17

Publication series

NameLecture Notes in Computer Science


Conference17th International Symposium on Fundamentals of Computation Theory, FCT 2009
Abbreviated titleFCT 2009


Dive into the research topics of 'Computing role assignments of chordal graphs'. Together they form a unique fingerprint.

Cite this