Computing role assignments of proper interval graphs in polynomial time

Pinar Heggernes; Pim van 't Hof; Daniël Paulusma

doi:10.1007/978-3-642-19222-7_18

Computing role assignments of proper interval graphs in polynomial time

Pinar Heggernes, Pim van 't Hof, Daniël Paulusma

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

39 Downloads (Pure)

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.

Original language	English
Title of host publication	Combinatorial Algorithms - 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers
Editors	Costas S. Iliopoulos, William F. Smyth
Publisher	Springer
Pages	167-180
Number of pages	14
ISBN (Electronic)	978-3-642-19222-7
ISBN (Print)	978-3-642-19221-0
DOIs	https://doi.org/10.1007/978-3-642-19222-7_18
Publication status	Published - 2010
Externally published	Yes
Event	21st International Workshop on Combinatorial Algorithms, IWOCA 2010 - London, United Kingdom Duration: 26 Jul 2010 → 28 Jul 2010 Conference number: 21

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	6460

Conference

Conference	21st International Workshop on Combinatorial Algorithms, IWOCA 2010
Abbreviated title	IWOCA 2010
Country/Territory	United Kingdom
City	London
Period	26/07/10 → 28/07/10

Access to Document

10.1007/978-3-642-19222-7_18

10.1007_978-3-642-19222-7_18Accepted author version, 452 KB

Cite this

Heggernes, P., van 't Hof, P., & Paulusma, D. (2010). 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, UK, July 26-28, 2010, Revised Selected Papers (pp. 167-180). (Lecture Notes in Computer Science; Vol. 6460). Springer. https://doi.org/10.1007/978-3-642-19222-7_18

@inproceedings{da2dcd498df6451a9e70349db05f1860,

title = "Computing role assignments of proper interval graphs in polynomial time",

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.",

author = "Pinar Heggernes and {van 't Hof}, Pim and Dani{\"e}l Paulusma",

year = "2010",

doi = "10.1007/978-3-642-19222-7_18",

language = "English",

isbn = "978-3-642-19221-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "167--180",

editor = "Iliopoulos, {Costas S.} and Smyth, {William F.}",

booktitle = "Combinatorial Algorithms - 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers",

address = "Germany",

note = "21st International Workshop on Combinatorial Algorithms, IWOCA 2010, IWOCA 2010 ; Conference date: 26-07-2010 Through 28-07-2010",

}

Heggernes, P, van 't Hof, P & Paulusma, D 2010, Computing role assignments of proper interval graphs in polynomial time. in CS Iliopoulos & WF Smyth (eds), Combinatorial Algorithms - 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers. Lecture Notes in Computer Science, vol. 6460, Springer, pp. 167-180, 21st International Workshop on Combinatorial Algorithms, IWOCA 2010, London, United Kingdom, 26/07/10. https://doi.org/10.1007/978-3-642-19222-7_18

Computing role assignments of proper interval graphs in polynomial time. / Heggernes, Pinar; van 't Hof, Pim; Paulusma, Daniël.
Combinatorial Algorithms - 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers. ed. / Costas S. Iliopoulos; William F. Smyth. Springer, 2010. p. 167-180 (Lecture Notes in Computer Science; Vol. 6460).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Computing role assignments of proper interval graphs in polynomial time

AU - Heggernes, Pinar

AU - van 't Hof, Pim

AU - Paulusma, Daniël

N1 - Conference code: 21

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-19222-7_18

DO - 10.1007/978-3-642-19222-7_18

M3 - Conference contribution

SN - 978-3-642-19221-0

T3 - Lecture Notes in Computer Science

SP - 167

EP - 180

BT - Combinatorial Algorithms - 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers

A2 - Iliopoulos, Costas S.

A2 - Smyth, William F.

PB - Springer

T2 - 21st International Workshop on Combinatorial Algorithms, IWOCA 2010

Y2 - 26 July 2010 through 28 July 2010

ER -

Heggernes P, van 't Hof P, Paulusma D. Computing role assignments of proper interval graphs in polynomial time. In Iliopoulos CS, Smyth WF, editors, Combinatorial Algorithms - 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers. Springer. 2010. p. 167-180. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-19222-7_18

Computing role assignments of proper interval graphs in polynomial time

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this