J. Fiala
A complete complexity classification of the role assignment problem
Fiala, J.; Paulusma, D.
Abstract
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.
Citation
Fiala, J., & Paulusma, D. (2005). A complete complexity classification of the role assignment problem. Theoretical Computer Science, 349(1), 67-81. https://doi.org/10.1016/j.tcs.2005.09.029
Journal Article Type | Article |
---|---|
Publication Date | 2005-12 |
Deposit Date | Apr 23, 2008 |
Journal | Theoretical Computer Science |
Print ISSN | 0304-3975 |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Volume | 349 |
Issue | 1 |
Pages | 67-81 |
DOI | https://doi.org/10.1016/j.tcs.2005.09.029 |
Keywords | Graph homomorphism. |
Public URL | https://durham-repository.worktribe.com/output/1608248 |
You might also like
Independent transversals versus transversals
(2019)
Conference Proceeding
Connected vertex cover for (sP1+P5)-free graphs
(2019)
Journal Article
Filling the complexity gaps for colouring planar and bounded degree graphs
(2019)
Journal Article
Finding a small number of colourful components
(2019)
Conference Proceeding
Clique-width for hereditary graph classes
(2019)
Journal Article