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

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 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
PublisherSpringer Singapore
Pages193-204
Number of pages12
DOIs
Publication statusPublished - 2009
Externally publishedYes
Event17th International Symposium on Fundamentals of Computation Theory, FCT 2009 - Wrocław, Poland
Duration: 2 Sep 20094 Sep 2009
Conference number: 17

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume5699

Conference

Conference17th International Symposium on Fundamentals of Computation Theory, FCT 2009
Abbreviated titleFCT 2009
CountryPoland
CityWrocław
Period2/09/094/09/09

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

Cite this