{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T09:40:22Z","timestamp":1740476422719,"version":"3.37.3"},"reference-count":30,"publisher":"EDP Sciences","issue":"1","license":[{"start":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T00:00:00Z","timestamp":1740441600000},"content-version":"vor","delay-in-days":55,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002322","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","id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2025,1,15]]},"published-print":{"date-parts":[[2025,1]]},"abstract":"<jats:p>We present the first results on the complexity of the reconfiguration of vertex separators under the three most popular rules: token addition\/removal, token jumping (TJ), and token sliding (TS). We show that, aside from some trivially negative instances, the first two rules are equivalent to each other. On the other hand, even if only on a subclass of bipartite graphs, TS is not equivalent to the other two unless NP = PSPACE; we do this by showing a relationship between separators and independent sets in this subclass of bipartite graphs. In terms of polynomial time algorithms, we show that every class with a polynomially bounded number of minimal vertex separators admits an efficient algorithm under token jumping, then turn our attention to two classes that do not meet this condition: {3<jats:italic>P<\/jats:italic><jats:sub>1<\/jats:sub>, <jats:italic>diamond<\/jats:italic>}-free and series-parallel graphs. For the first, we describe a novel characterization, which we use to show that reconfiguring vertex separators under token jumping is always possible and that, under token sliding, it can be done in polynomial time; for series-parallel graphs, we also prove that reconfiguration is always possible under TJ and exhibit a polynomial time algorithm to construct the reconfiguration sequence.<\/jats:p>","DOI":"10.1051\/ro\/2025006","type":"journal-article","created":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T19:48:34Z","timestamp":1737143314000},"page":"725-742","source":"Crossref","is-referenced-by-count":0,"title":["Some results on vertex separator reconfiguration"],"prefix":"10.1051","volume":"59","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5164-1460","authenticated-orcid":false,"given":"Guilherme","family":"de Castro Mendes Gomes","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S\u00e9rgio Henrique","family":"Nogueira","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vinicius Fernandes","family":"dos Santos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2025,2,25]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Berry A., Bordat J.P. and Cogis O., Generating all the minimal separators of a graph, in Graph-Theoretic Concepts in Computer Science, edited by Widmayer P., Neyer G. and Eidenbenz S.. Springer Berlin Heidelberg, Berlin, Heidelberg (1999) 167\u2013172.","DOI":"10.1007\/3-540-46784-X_17"},{"key":"R2","unstructured":"Bonamy M. and Bousquet N., Reconfiguring independent sets in cographs. Preprint arXiv:14061433."},{"key":"R3","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1007\/s10878-012-9490-y","volume":"27","author":"Bonamy","year":"2012","journal-title":"J. Comb. Optim"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Bondy J.A. and Murty U.S.R., Graph Theory. Springer Publishing Company, Incorporated (2008).","DOI":"10.1007\/978-1-84628-970-5"},{"key":"R5","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1002\/jgt.21992","volume":"83","author":"Bonsma","year":"2016","journal-title":"J. Graph Theory"},{"key":"R6","doi-asserted-by":"crossref","first-page":"5215","DOI":"10.1016\/j.tcs.2009.08.023","volume":"410","author":"Bonsma","year":"2009","journal-title":"Theor. Comput. Sci"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Bonsma P., Kami\u0144ski M. and Wrochna M., Reconfiguring independent sets in claw-free graphs, in Algorithm Theory\u2013 SWAT 2014: 14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2\u20134, 2014. Proceedings 14. Springer (2014) 86\u201397.","DOI":"10.1007\/978-3-319-08404-6_8"},{"key":"R8","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1002\/jgt.20514","volume":"67","author":"Cereceda","year":"2011","journal-title":"J Graph Theory"},{"key":"R9","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/j.tcs.2015.07.037","volume":"600","author":"Demaine","year":"2015","journal-title":"Theor. Comput. Sci"},{"key":"R10","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0022-247X(65)90125-3","volume":"10","author":"Duffin","year":"1965","journal-title":"J. Math. Anal. App"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"Gharibian S. and Sikora J., Ground state connectivity of local hamiltonians, in Automata, Languages, and Programming, edited by Halld\u00f3rsson M.M., Iwama K., Kobayashi N. and Speckmann B.. Springer Berlin Heidelberg, Berlin, Heidelberg (2015) 617\u2013628.","DOI":"10.1007\/978-3-662-47672-7_50"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Gopalan P., Kolaitis P.G., Maneva E.N. and Papadimitriou C.H., The connectivity of boolean satisfiability: compu- tational and structural dichotomies, in Automata, Languages and Programming, edited by Bugliesi M., Preneel B., Sassone V. and Wegener I.. Springer Berlin Heidelberg, Berlin, Heidelberg (2006) 346\u2013357.","DOI":"10.1007\/11786986_31"},{"key":"R13","doi-asserted-by":"crossref","first-page":"2330","DOI":"10.1137\/07070440X","volume":"38","author":"Gopalan","year":"2009","journal-title":"SIAM J. Comput"},{"key":"R14","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1016\/j.tcs.2005.05.008","volume":"343","author":"Hearn","year":"2005","journal-title":"Theor. Comput. Sci"},{"key":"R15","doi-asserted-by":"crossref","first-page":"1054","DOI":"10.1016\/j.tcs.2010.12.005","volume":"412","author":"Ito","year":"2011","journal-title":"Theor. Comput. Sci"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"Ito T., Kami\u0144ski M., Ono H., Suzuki A., Uehara R. and Yamanaka K., On the parameterized complexity for token jumping on graphs, in International Conference on Theory and Applications of Models of Computation. Springer International Publishing, Cham (2014) 341\u2013351.","DOI":"10.1007\/978-3-319-06089-7_24"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"Ito T., Ono H. and Otachi Y., Reconfiguration of cliques in a graph, in Theory and Applications of Models of Computation, edited by Jain R., Jain S. and Stephan F.. Springer International Publishing, Cham (2015) 212\u2013223.","DOI":"10.1007\/978-3-319-17142-5_19"},{"key":"R18","doi-asserted-by":"crossref","first-page":"397","DOI":"10.2307\/2369492","volume":"2","author":"Johnson and W.E. Story","year":"1879","journal-title":"Am. J. Math"},{"key":"R19","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/j.tcs.2012.03.004","volume":"439","author":"Kami\u0144ski","year":"2012","journal-title":"Theor. Comput. Sci"},{"key":"R20","unstructured":"Kanj and G. Xia I., Flip distance is in FPT time O(n + k \u00b7 ck), in 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2015)."},{"key":"R21","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/S0166-218X(98)00123-1","volume":"89","author":"Kumar and C. Madhavan","year":"1998","journal-title":"Discrete Appl. Math"},{"key":"R22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3280825","volume":"15","author":"Lokshtanov and A.E. Mouawad","year":"2018","journal-title":"ACM Trans. Algorithms"},{"key":"R23","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/j.comgeo.2014.11.001","volume":"49","author":"Lubiw","year":"2015","journal-title":"Comput. Geom"},{"key":"R24","doi-asserted-by":"crossref","first-page":"4613","DOI":"10.1016\/j.tcs.2011.04.041","volume":"412","author":"Makino","year":"2011","journal-title":"Theor. Comput. Sci"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"Milani\u010d M. and Piva\u010d N., Minimal separators in graph classes defined by small forbidden induced subgraphs, in Graph-Theoretic Concepts in Computer Science. Springer International Publishing, Cham (2019) 379\u2013391.","DOI":"10.1007\/978-3-030-30786-8_29"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"Mouawad A.E., Nishimura N., Raman V. and Wrochna M., Reconfiguration over tree decompositions, in Interna- tional Symposium on Parameterized and Exact Computation. Springer (2014) 246\u2013257.","DOI":"10.1007\/978-3-319-13524-3_21"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"Mouawad A.E., Nishimura N., Pathak V. and Raman V., Shortest reconfiguration paths in the solution space of boolean formulas, in Automata, Languages, and Programming, edited by MHalld\u00f3rsson M., Iwama K., Kobayashi N. and Speckmann B.. Springer Berlin Heidelberg, Berlin, Heidelberg (2015) 985\u2013996.","DOI":"10.1007\/978-3-662-47672-7_80"},{"key":"R28","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1007\/s00453-016-0159-2","volume":"78","author":"Mouawad","year":"2016","journal-title":"Algorithmica"},{"key":"R29","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1002\/net.3230130202","volume":"13","author":"Wald","year":"1983","journal-title":"Networks"},{"key":"R30","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jcss.2017.11.003","volume":"93","author":"Wrochna","year":"2018","journal-title":"J. Comput. Syst. Sci"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2025006\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T08:54:00Z","timestamp":1740473640000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2025006"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1]]},"references-count":30,"journal-issue":{"issue":"1"},"alternative-id":["ro230078"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2025006","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"2804-7303"}],"subject":[],"published":{"date-parts":[[2025,1]]}}}