Minimum Separator Reconfiguration
share
We study the problem of reconfiguring one minimum s-t-separator A into another minimum s-t-separator B in some n-vertex graph G containing two non-adjacent vertices s and t. We consider several variants of the problem as we focus on both the token sliding and token jumping models. Our first contribution is a polynomial-time algorithm that computes (if one exists) a minimum-length sequence of slides transforming A into B. We additionally establish that the existence of a sequence of jumps (which need not be of minimum length) can be decided in polynomial time (by an algorithm that also outputs a witnessing sequence when one exists). In contrast, and somewhat surprisingly, we show that deciding if a sequence of at most ℓ jumps can transform A into B is an -complete problem. To complement this negative result, we investigate the parameterized complexity of what we believe to be the two most natural parameterized counterparts of the latter problem; in particular, we study the problem of computing a minimum-length sequence of jumps when parameterized by the size k of the minimum and when parameterized by the number of jumps ℓ. For the first parameterization, we show that the problem is fixed-parameter tractable, but does not admit a polynomial kernel unless ⊆. We complete the picture by designing a kernel with 𝒪(ℓ^2) vertices and edges for the length ℓ of the sequence as a parameter.
READ FULL TEXT
