{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,23]],"date-time":"2026-02-23T13:41:58Z","timestamp":1771854118433,"version":"3.50.1"},"reference-count":21,"publisher":"EDP Sciences","issue":"3","license":[{"start":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T00:00:00Z","timestamp":1683763200000},"content-version":"vor","delay-in-days":10,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005285","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado de Goi\u00e1s","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100005285","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2023,4,3]]},"published-print":{"date-parts":[[2023,5]]},"abstract":"<jats:p>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 <jats:italic>r<\/jats:italic>-Role Assignment whose goal is deciding whether it exists such an assignment of <jats:italic>r<\/jats:italic> distinct roles. This problem is known to be <jats:bold>NP<\/jats:bold>-complete for any fixed <jats:italic>r<\/jats:italic>\u00a0\u2265\u00a02. The Cartesian product of graphs is a well studied graph operation, often used for modeling interconnection networks. Formally, the <jats:italic>Cartesian product<\/jats:italic> of <jats:italic>G<\/jats:italic> and <jats:italic>H<\/jats:italic> is a graph, denoted as <jats:italic>G<\/jats:italic>\u25a1<jats:italic>H<\/jats:italic>, whose vertex set is <jats:italic>V<\/jats:italic>(<jats:italic>G<\/jats:italic>)\u00a0\u00d7\u00a0<jats:italic>V<\/jats:italic>(<jats:italic>H<\/jats:italic>) and two vertices (<jats:italic>u<\/jats:italic>, <jats:italic>v<\/jats:italic>) and (<jats:italic>x<\/jats:italic>,\u00a0<jats:italic>y<\/jats:italic>) are adjacent precisely if <jats:italic>u<\/jats:italic> = <jats:italic>x<\/jats:italic> and <jats:italic>vy<\/jats:italic> \u2208\u00a0<jats:italic>E<\/jats:italic>(<jats:italic>H<\/jats:italic>), or <jats:italic>ux<\/jats:italic>\u00a0\u2208\u00a0<jats:italic>E<\/jats:italic>(<jats:italic>G<\/jats:italic>) and <jats:italic>v<\/jats:italic> = <jats:italic>y<\/jats:italic>. In a previous work, we showed that Cartesian product of graphs are always 2-role assignable, however the 3-Role Assignment problem is <jats:bold>NP<\/jats:bold>-complete on this class. In this paper, we prove that <jats:italic>r<\/jats:italic>-Role Assignment restricted to Cartesian product graphs is still <jats:bold>NP<\/jats:bold>-complete, for any fixed <jats:italic>r<\/jats:italic> \u2265 4.<\/jats:p>","DOI":"10.1051\/ro\/2023047","type":"journal-article","created":{"date-parts":[[2023,4,7]],"date-time":"2023-04-07T07:23:00Z","timestamp":1680852180000},"page":"1075-1086","source":"Crossref","is-referenced-by-count":3,"title":["Computing role assignments of Cartesian product of graphs"],"prefix":"10.1051","volume":"57","author":[{"given":"Diane","family":"Castonguay","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1132-1518","authenticated-orcid":false,"given":"Elis\u00e2ngela Silva","family":"Dias","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2010-4088","authenticated-orcid":false,"given":"Fernanda Neiva","family":"Mesquita","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3002-5172","authenticated-orcid":false,"given":"Julliano Rosa","family":"Nascimento","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2023,5,11]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Angluin D., Local and global properties in networks of processors, in Proc. 12th ACM Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing (1980) 82\u201393.","DOI":"10.1145\/800141.804655"},{"key":"R2","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1051\/ro\/2021192","volume":"56","author":"Castonguay","year":"2022","journal-title":"RAIRO-Oper. Res."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Chalopin J., M\u00e9tivier Y. and Zielonka W., Election, naming and cellular edge local computations, in International Conference on Graph Transformation (ICGT 2004) (EATCS best paper award), Sep. Italy. Springer (2004) 242\u2013256.","DOI":"10.1007\/978-3-540-30203-2_18"},{"key":"R4","first-page":"85","volume":"74","author":"Chalopin","year":"2006","journal-title":"Fundam. Inf."},{"key":"R5","first-page":"193","volume":"112","author":"de Almeida","year":"2013","journal-title":"ARS Comb."},{"key":"R6","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1016\/j.tcs.2016.05.011","volume":"635","author":"Dourado","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"R7","first-page":"257","volume":"33","author":"Dunbar","year":"2000","journal-title":"J. Comb. Math. Comb. Comput."},{"key":"R8","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/0165-4896(91)90080-B","volume":"21","author":"Everett","year":"1991","journal-title":"Math. Soc. Sci."},{"key":"R9","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.tcs.2005.09.029","volume":"349","author":"Fiala","year":"2005","journal-title":"Theor. Comput. Sci."},{"key":"R10","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1007\/s00224-009-9200-z","volume":"46","author":"Fiala","year":"2010","journal-title":"Theory Comput. Syst."},{"key":"R11","unstructured":"Garey M.R. and Johnson D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Co., New York, USA (1979)."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Hammack R.H., Imrich W. and Klav\u017ear S., Handbook of Product Graphs. Vol. 2. CRC Press, Boca Raton (2011).","DOI":"10.1201\/b10959"},{"key":"R13","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/j.jda.2011.12.004","volume":"14","author":"Heggernes","year":"2012","journal-title":"J. Discrete Algorithms"},{"key":"R14","doi-asserted-by":"crossref","first-page":"1633","DOI":"10.1007\/s00373-019-02082-7","volume":"35","author":"Kaul","year":"2019","journal-title":"Graphs Comb."},{"key":"R15","doi-asserted-by":"crossref","first-page":"1219","DOI":"10.1016\/j.compstruc.2007.11.005","volume":"86","author":"Kaveh","year":"2008","journal-title":"Comput. Struct."},{"key":"R16","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1016\/j.dam.2008.03.003","volume":"157","author":"Laskar","year":"2009","journal-title":"Discrete Appl. Math."},{"key":"R17","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/S0165-4896(00)00064-0","volume":"41","author":"Peke\u010d","year":"2001","journal-title":"Math. Soc. Sci."},{"key":"R18","first-page":"67","volume":"37","author":"Roberts","year":"2001","journal-title":"Netw. Int. J."},{"key":"R19","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1007\/BF01162967","volume":"72","author":"Sabidussi","year":"1959","journal-title":"Math. Z."},{"key":"R20","doi-asserted-by":"crossref","first-page":"3601","DOI":"10.1016\/j.tcs.2010.05.041","volume":"411","author":"van \u2018t Hof","year":"2010","journal-title":"Theor. Comput. Sci."},{"key":"R21","unstructured":"Zhao Y.-Q., Feng W.-L., Li H. and Yang J.-M., k-role assignments under some graph operations. J. Hebei Univ Sci. Technol. (2010) 06."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2023047\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T08:23:39Z","timestamp":1683793419000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2023047"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5]]},"references-count":21,"journal-issue":{"issue":"3"},"alternative-id":["ro220060"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2023047","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"2804-7303","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5]]}}}