P. Heggernes
Computing Role Assignments of Proper Interval Graphs in Polynomial Time
Heggernes, P.; Hof, van't P.; Paulusma, D.
Authors
Contributors
Costas S. Iliopoulos
Editor
William F. Smyth
Editor
Abstract
A homomorphism from a graph G to a graph R is locally surjective if its restriction to the neighborhood of each vertex of G is surjective. Such a homomorphism is also called an R-role assignment of G. Role assignments have applications in distributed computing, social network theory, and topological graph theory. The Role Assignment problem has as input a pair of graphs (G,R) and asks whether G has an R-role assignment. This problem is NP-complete already on input pairs (G,R) where R is a path on three vertices. So far, the only known non-trivial tractable case consists of input pairs (G,R) where G is a tree. We present a polynomial time algorithm that solves Role Assignment on all input pairs (G,R) where G is a proper interval graph. Thus we identify the first graph class other than trees on which the problem is tractable. As a complementary result, we show that the problem is Graph Isomorphism-hard on chordal graphs, a superclass of proper interval graphs and trees.
Citation
Heggernes, P., Hof, V. P., & Paulusma, D. (2011). Computing Role Assignments of Proper Interval Graphs in Polynomial Time. In C. S. Iliopoulos, & W. F. Smyth (Eds.), Combinatorial algorithms : 21st International Workshop, IWOCA 2010, London, July 26-28, 2010, revised selected papers (167-180). https://doi.org/10.1007/978-3-642-19222-7_18
Conference Name | 21st International Workshop on Combinatorial Algorithms, IWOCA 2010 |
---|---|
Conference Location | London |
Publication Date | Jan 1, 2011 |
Deposit Date | Dec 21, 2014 |
Publicly Available Date | Mar 29, 2024 |
Pages | 167-180 |
Series Title | Lecture notes in computer science |
Series Number | 6460 |
Series ISSN | 0302-9743,1611-3349 |
Book Title | Combinatorial algorithms : 21st International Workshop, IWOCA 2010, London, July 26-28, 2010, revised selected papers |
ISBN | 9783642192210 |
DOI | https://doi.org/10.1007/978-3-642-19222-7_18 |
Public URL | https://durham-repository.worktribe.com/output/1153773 |
Files
Accepted Conference Proceeding
(375 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-19222-7_18
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
An algorithmic framework for locally constrained homomorphisms
(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
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