Computing role assignments of chordal graphs

Hof, P van 't; Paulusma, D.; Rooij, J.M.M. van

doi:10.1016/j.tcs.2010.05.041

Computing role assignments of chordal graphs

Hof, P van 't; Paulusma, D.; Rooij, J.M.M. van

Authors

P van 't Hof

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

J.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≥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.

Citation

Hof, P. V. '., Paulusma, D., & Rooij, J. V. (2010). Computing role assignments of chordal graphs. Theoretical Computer Science, 411(40-42), 3601-3613. https://doi.org/10.1016/j.tcs.2010.05.041

Journal Article Type	Article
Publication Date	Sep 1, 2010
Deposit Date	Oct 6, 2010
Publicly Available Date	Oct 7, 2010
Journal	Theoretical Computer Science
Print ISSN	0304-3975
Publisher	Elsevier
Peer Reviewed	Peer Reviewed
Volume	411
Issue	40-42
Pages	3601-3613
DOI	https://doi.org/10.1016/j.tcs.2010.05.041
Keywords	Role assignment, Graph homomorphism, Chordal graph, Computational complexity.
Public URL	https://durham-repository.worktribe.com/output/1515716