We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

A complete complexity classification of the role assignment problem.

Fiala, J. and Paulusma, Daniel (2005) 'A complete complexity classification of the role assignment problem.', Theoretical computer science., 349 (1). pp. 67-81.


In social network theory a society is often represented by a simple graph G, where vertices stand for individuals and edges represent relationships between those individuals. The description of the social network is tried to be simplified by assigning roles to the individuals, such that the neighborhood relation is preserved. Formally, for a fixed graph R we ask for a vertex mapping r:VG→VR, such that r(NG(u))=NR(r(u)) for all uVG. If such a mapping exists the graph G is called R-role assignable and the corresponding decision problem is called the R-role assignment problem. Kristiansen and Telle conjectured that the R-role assignment problem is an -complete problem for any simple connected graph R on at least three vertices. In this paper we prove their conjecture. In addition, we determine the computational complexity of the role assignment problem for nonsimple and disconnected role graphs, as these are considered in social network theory as well.

Item Type:Article
Keywords:Graph homomorphism.
Full text:Full text not available from this repository.
Publisher Web site:
Date accepted:No date available
Date deposited:No date available
Date of first online publication:December 2005
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar