论文标题
在顶点分离器重新配置上的一些结果
Some results on Vertex Separator Reconfiguration
论文作者
论文摘要
我们介绍了有关在三个最流行的规则下重新配置顶点分离器的复杂性的第一个结果：令牌加法/删除，象征性跳转和令牌滑动。我们表明，除了一些琐碎的负面实例之外，前两个规则彼此等同，即使仅在二分化图的子类上，TJ也不等于其他两个，除非$ \ mathsf {np} = \ mathsf {pspace} $;我们通过在这个两部分图的子类中显示分离器与独立集之间的关系来做到这一点。在多项式时间算法方面，我们表明每个具有多项式界数的最小顶点分离器的类都在令牌跳跃下的有效算法，然后将我们的注意力转向不符合此条件的两个类：$ \ {3p_1，dimond \}，钻石\} $ - 免费和系列 - 和系列 - 帕尔平行图。首先，我们描述了一种新颖的表征，我们用来证明在令牌跳跃下的重新配置的顶点分离器总是可能的，并且在令牌滑动下，可以在多项式时间内完成。对于串联平行图，我们还证明在TJ下始终可能进行重新配置，并显示多项式时间算法以构建重新配置序列。
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 $\mathsf{NP} = \mathsf{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_1, 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.
