{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:46:54Z","timestamp":1759063614608,"version":"3.37.3"},"reference-count":19,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","funder":[{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["303726\/2017-2"],"award-info":[{"award-number":["303726\/2017-2"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004586","name":"Funda\u00e7\u00e3o Carlos Chagas Filho de Amparo \u00e0 Pesquisa do Estado do Rio de Janeiro","doi-asserted-by":"publisher","award":["E-26\/203.272\/2017"],"award-info":[{"award-number":["E-26\/203.272\/2017"]}],"id":[{"id":"10.13039\/501100004586","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","award":["Finance Code 001"],"award-info":[{"award-number":["Finance Code 001"]}],"id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p> Complementary prism graphs arise from the disjoint union of a graph [Formula: see text] and its complement [Formula: see text] by adding the edges of a perfect matching joining pairs of corresponding vertices of [Formula: see text] and [Formula: see text]. Classical graph problems such as Clique and Independent Set were proved to be NP-complete on such a class of graphs. In this work, we study the complexity of both problems on complementary prism graphs from the parameterized complexity point of view. First, we prove that both problems admit a kernel and therefore are fixed-parameter tractable (FPT) when parameterized by the size of the solution, [Formula: see text]. Then, we show that [Formula: see text]-Clique and [Formula: see text]-Independent Set on complementary prisms do not admit polynomial kernel when parameterized by [Formula: see text], unless [Formula: see text]. Furthermore, we address the [Formula: see text]-Contamination problem in the context of complementary prisms. This problem consists in completely contaminating a given graph [Formula: see text] using a minimum set of initially infected vertices. For a vertex to be contaminated, it is enough that at least two of its neighbors are contaminated. The propagation of the contamination follows this rule until no more vertex can be contaminated. It is known that the minimum set of initially contaminated vertices necessary to contaminate a complementary prism of connected graphs [Formula: see text] and [Formula: see text] has cardinality at most [Formula: see text]. In this paper, we show that the tight upper bound for this invariant on complementary prisms is [Formula: see text], improving a result of Duarte et al. (2017). <\/jats:p>","DOI":"10.1142\/s0129054121500027","type":"journal-article","created":{"date-parts":[[2021,1,7]],"date-time":"2021-01-07T14:03:41Z","timestamp":1610028221000},"page":"37-52","source":"Crossref","is-referenced-by-count":4,"title":["Remarks on k-Clique, k-Independent Set and 2-Contamination in Complementary Prisms"],"prefix":"10.1142","volume":"32","author":[{"given":"Priscila P.","family":"Camargo","sequence":"first","affiliation":[{"name":"Instituto de Computa\u00e7\u00e3o, Universidade Federal Fluminense, Niter\u00f3i, RJ, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5320-9209","authenticated-orcid":false,"given":"U\u00e9verton S.","family":"Souza","sequence":"additional","affiliation":[{"name":"Instituto de Computa\u00e7\u00e3o, Universidade Federal Fluminense, Niter\u00f3i, RJ, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3002-5172","authenticated-orcid":false,"given":"Julliano R.","family":"Nascimento","sequence":"additional","affiliation":[{"name":"Instituto de Inform\u00e1tica, Universidade Federal de Goi\u00e1s, Goi\u00e2nia, GO, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2021,1,6]]},"reference":[{"key":"S0129054121500027BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.11.006"},{"issue":"4","key":"S0129054121500027BIB004","volume":"21","author":"Castonguay D.","year":"2019","journal-title":"Discr. Math. Theor. Comput. Sci."},{"key":"S0129054121500027BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2018.12.007"},{"key":"S0129054121500027BIB006","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.03.029"},{"key":"S0129054121500027BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"S0129054121500027BIB008","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume":"87","author":"Downey R. G.","year":"1999","journal-title":"Monogr. Comput. Sci. Springer, New York"},{"key":"S0129054121500027BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.09.012"},{"key":"S0129054121500027BIB010","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-015-9968-5"},{"key":"S0129054121500027BIB011","first-page":"463","volume":"2","author":"Erd\u00f6s P.","year":"1935","journal-title":"Compositio Mathematica"},{"volume-title":"Parameterized Complexity Theory","year":"2006","author":"Flum J.","key":"S0129054121500027BIB012"},{"key":"S0129054121500027BIB013","first-page":"21","volume":"51","author":"Haynes T. W.","year":"2007","journal-title":"Bulletin of the Institute of Combinatorics and Its Applications"},{"key":"S0129054121500027BIB014","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-007-9135-8"},{"issue":"1","key":"S0129054121500027BIB015","first-page":"31","volume":"14","author":"Janseana P.","year":"2015","journal-title":"Thai J. Math."},{"issue":"4","key":"S0129054121500027BIB016","first-page":"19","volume":"10","author":"Kratsch S.","year":"2014","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"S0129054121500027BIB017","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2015.04.016"},{"key":"S0129054121500027BIB018","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"S0129054121500027BIB019","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.10.003"},{"key":"S0129054121500027BIB020","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-30.1.264"},{"issue":"3","key":"S0129054121500027BIB021","first-page":"1071","volume":"88","author":"Zatesko L. M.","year":"2019","journal-title":"Acta Mathematica Universitatis Comenianae"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054121500027","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,19]],"date-time":"2021-02-19T08:38:46Z","timestamp":1613723926000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054121500027"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":19,"journal-issue":{"issue":"01","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1142\/S0129054121500027"],"URL":"https:\/\/doi.org\/10.1142\/s0129054121500027","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}