Computing role assignments of chordal graphs

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

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.

Citation

Hof, P. V. '., Paulusma, D., & Rooij, J. V. (2009, September). Computing role assignments of chordal graphs. Presented at 17th International Symposium on Fundamentals of Computation Theory (FCT 2009), Wroclaw, Poland

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 17th International Symposium on Fundamentals of Computation Theory (FCT 2009)
• Start Date: Sep 2, 2009
• End Date: Sep 4, 2009
• Publication Date: Sep 19, 2009
• Deposit Date: Oct 15, 2009
• Print ISSN: 0302-9743
• Pages: 193-204
• Series Title: Lecture notes in computer science
• Series Number: 5699
• Series ISSN: 0302-9743,1611-3349
• Book Title: Fundamentals of computation theory : 17th International Symposium, FCT 2009, Wrocław, Poland, September 2-4, 2009. Proceedings.
• DOI: https://doi.org/10.1007/978-3-642-03409-1_18
• Public URL: https://durham-repository.worktribe.com/output/1160552