Issue |
RAIRO-Oper. Res.
Volume 57, Number 3, May-June 2023
|
|
---|---|---|
Page(s) | 1075 - 1086 | |
DOI | https://doi.org/10.1051/ro/2023047 | |
Published online | 11 May 2023 |
Computing role assignments of Cartesian product of graphs
Instituto de Informática, Universidade Federal de Goiás, Goiás, Brazil
* Corresponding author: fernandaneivamesquita@inf.ufg.br
Received:
1
February
2022
Accepted:
3
April
2023
Network science is a growing field of study using Graph Theory as a modeling tool. In social networks, a role assignment is such that individuals play the same role, if they relate in the same way to other individuals playing counterpart roles. In this sense, a role assignment permit to represent the network through a smaller graph modeling its roles. This leads to a problem called r-Role Assignment whose goal is deciding whether it exists such an assignment of r distinct roles. This problem is known to be NP-complete for any fixed r ≥ 2. The Cartesian product of graphs is a well studied graph operation, often used for modeling interconnection networks. Formally, the Cartesian product of G and H is a graph, denoted as G□H, whose vertex set is V(G) × V(H) and two vertices (u, v) and (x, y) are adjacent precisely if u = x and vy ∈ E(H), or ux ∈ E(G) and v = y. In a previous work, we showed that Cartesian product of graphs are always 2-role assignable, however the 3-Role Assignment problem is NP-complete on this class. In this paper, we prove that r-Role Assignment restricted to Cartesian product graphs is still NP-complete, for any fixed r ≥ 4.
Mathematics Subject Classification: 05C78 / 05C76 / 68Q25 / 05C15
Key words: Role assignment / Cartesian product / computational complexity
© The authors. Published by EDP Sciences, ROADEF, SMAI 2023
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.