Some results on vertex separator reconfiguration

¹ Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, Belo Horizonte, Brazil
² Instituto de Ciências Exatas e Tecnológicas, Universidade Federal de Viçosa IEF/UFV-CAF, Florestal, Brazil
³ Centro Federal de Educação Tecnológica de Minas Gerais CEFET/MG, Belo Horizonte, Brazil

^* Corresponding author: gcm.gomes@dcc.ufmg.br

Received: 27 January 2023
Accepted: 15 January 2025

Abstract

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: {3P₁, diamond}-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.