P van 't Hof
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 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 |
Files
Accepted Journal Article
(489 Kb)
PDF
Copyright Statement
NOTICE: this is the author's version of a work that was accepted for publication in Theoretical computer science.
You might also like
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Computing Subset Vertex Covers in H-Free Graphs
(2023)
Conference Proceeding
Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
(2023)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search