2020/04/22 by Guilherme C. M. Gomes, Gomes, Guilherme C. M., Sérgio H. Nogueira +3
Computer Science · #Algorithms and Data Compression #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Interconnection Networks and Systems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2004.10873
openalex publication_date 2020/04/22 · openalex created_date 2020/05/01 · openalex updated_date 2026/07/28
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, and token sliding. We show that, aside from some trivially negative instances, the first two rules are equivalent to each other and that, even if only on a subclass of bipartite graphs, TJ 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: \3P1, 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.