Computing role assignments of chordal graphs

Pim van 't Hof; Daniël Paulusma; Johan M. M. van Rooij

doi:10.1007/978-3-642-03409-1_18

Computing role assignments of chordal graphs

Pim van 't Hof, Daniël Paulusma, Johan M. M. van Rooij

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

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 becomes polynomially solvable for k = 2, but remains NP-complete for any k ≥ 3. This generalizes results of Sheng and answers his open problem.

Original language	English
Title of host publication	Fundamentals of Computation Theory, 17th International Symposium, FCT 2009, Wroclaw, Poland, September 2-4, 2009. Proceedings
Editors	Miroslaw Kutylowski, Witold Charatonik, Maciej Gebala
Publisher	Springer
Pages	193-204
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-03409-1_18
Publication status	Published - 2009
Externally published	Yes
Event	17th International Symposium on Fundamentals of Computation Theory, FCT 2009 - Wrocław, Poland Duration: 2 Sept 2009 → 4 Sept 2009 Conference number: 17

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	5699

Conference

Conference	17th International Symposium on Fundamentals of Computation Theory, FCT 2009
Abbreviated title	FCT 2009
Country/Territory	Poland
City	Wrocław
Period	2/09/09 → 4/09/09

Access to Document

10.1007/978-3-642-03409-1_18

Cite this

van 't Hof, P., Paulusma, D., & Rooij, J. M. M. V. (2009). Computing role assignments of chordal graphs. In M. Kutylowski, W. Charatonik, & M. Gebala (Eds.), Fundamentals of Computation Theory, 17th International Symposium, FCT 2009, Wroclaw, Poland, September 2-4, 2009. Proceedings (pp. 193-204). (Lecture Notes in Computer Science; Vol. 5699). Springer. https://doi.org/10.1007/978-3-642-03409-1_18

@inproceedings{b547e0f0f9fa492ba16bd8422456471c,

title = "Computing role assignments of chordal graphs",

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 becomes polynomially solvable for k = 2, but remains NP-complete for any k ≥ 3. This generalizes results of Sheng and answers his open problem.",

author = "{van 't Hof}, Pim and Dani{\"e}l Paulusma and Rooij, {Johan M. M. van}",

year = "2009",

doi = "10.1007/978-3-642-03409-1_18",

language = "English",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "193--204",

editor = "Miroslaw Kutylowski and Witold Charatonik and Maciej Gebala",

booktitle = "Fundamentals of Computation Theory, 17th International Symposium, FCT 2009, Wroclaw, Poland, September 2-4, 2009. Proceedings",

note = "17th International Symposium on Fundamentals of Computation Theory, FCT 2009, FCT 2009 ; Conference date: 02-09-2009 Through 04-09-2009",

}

van 't Hof, P, Paulusma, D & Rooij, JMMV 2009, Computing role assignments of chordal graphs. in M Kutylowski, W Charatonik & M Gebala (eds), Fundamentals of Computation Theory, 17th International Symposium, FCT 2009, Wroclaw, Poland, September 2-4, 2009. Proceedings. Lecture Notes in Computer Science, vol. 5699, Springer, pp. 193-204, 17th International Symposium on Fundamentals of Computation Theory, FCT 2009, Wrocław, Poland, 2/09/09. https://doi.org/10.1007/978-3-642-03409-1_18

Computing role assignments of chordal graphs. / van 't Hof, Pim; Paulusma, Daniël; Rooij, Johan M. M. van.
Fundamentals of Computation Theory, 17th International Symposium, FCT 2009, Wroclaw, Poland, September 2-4, 2009. Proceedings. ed. / Miroslaw Kutylowski; Witold Charatonik; Maciej Gebala. Springer, 2009. p. 193-204 (Lecture Notes in Computer Science; Vol. 5699).

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

TY - GEN

T1 - Computing role assignments of chordal graphs

AU - van 't Hof, Pim

AU - Paulusma, Daniël

AU - Rooij, Johan M. M. van

N1 - Conference code: 17

PY - 2009

Y1 - 2009

N2 - 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 becomes polynomially solvable for k = 2, but remains NP-complete for any k ≥ 3. This generalizes results of Sheng and answers his open problem.

AB - 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 becomes polynomially solvable for k = 2, but remains NP-complete for any k ≥ 3. This generalizes results of Sheng and answers his open problem.

U2 - 10.1007/978-3-642-03409-1_18

DO - 10.1007/978-3-642-03409-1_18

M3 - Conference contribution

T3 - Lecture Notes in Computer Science

SP - 193

EP - 204

BT - Fundamentals of Computation Theory, 17th International Symposium, FCT 2009, Wroclaw, Poland, September 2-4, 2009. Proceedings

A2 - Kutylowski, Miroslaw

A2 - Charatonik, Witold

A2 - Gebala, Maciej

PB - Springer

T2 - 17th International Symposium on Fundamentals of Computation Theory, FCT 2009

Y2 - 2 September 2009 through 4 September 2009

ER -

Computing role assignments of chordal graphs

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this