标题： 带重新配置问题及其对支配集重新配置的影响 显示英文标题

标题： The tape reconfiguration problem and its consequences for dominating set reconfiguration

摘要： 图$G=(V,E)$的一个支配集是一组顶点$D \subseteq V$，它们的闭邻域是$V$，即$N[D]=V$。 我们将支配集看作放置在$D$顶点上的令牌集合。 在支配集重新配置问题的滑动令牌变体（TS-DSR）中，我们通过沿边滑动令牌，将源支配集转换为目标支配集，并在整个变换过程中始终保持支配集，目标是在$G$内完成这一过程。 TS-DSR 对于路径宽度为$w$的图来说，已知是 PSPACE 完全的，对于某个非显式常数$w$来说也是如此，并且根据解的大小$k$参数化时是 XL 完全的。本文的第一贡献在于使用一种新颖的方法来提供第一个显式的常数，使得 TS-DSR 问题是 PSPACE 完全的，这个问题在文献中一直是开放的。 从参数复杂性的角度来看，当参数化为无处稠密类图上的支配集大小时，DSR 的令牌跳跃变体已知是 FPT（固定参数可 tractable）。但是，相比之下，关于 TS-DSR 没有已知的非平凡结果。我们证明了 DSR 在滑动模型中实际上更难，因为它在有界路径宽度图上是 XL 完全的，即使参数化为$k$加上图的反馈顶点集数也是如此。这首次在有界树宽图上的问题复杂性方面提供了滑动令牌和跳跃令牌之间行为差异的例子。 我们所有的结果都是通过一种全新的方法获得的，该方法基于所谓的磁带重配置问题的难度，我们认为这个问题本身具有独立的研究兴趣。 显示英文摘要

摘要： A dominating set of a graph $G=(V,E)$ is a set of vertices $D \subseteq V$ whose closed neighborhood is $V$, i.e., $N[D]=V$. We view a dominating set as a collection of tokens placed on the vertices of $D$. In the token sliding variant of the Dominating Set Reconfiguration problem (TS-DSR), we seek to transform a source dominating set into a target dominating set in $G$ by sliding tokens along edges, and while maintaining a dominating set all along the transformation. TS-DSR is known to be PSPACE-complete even restricted to graphs of pathwidth $w$, for some non-explicit constant $w$ and to be XL-complete parameterized by the size $k$ of the solution. The first contribution of this article consists in using a novel approach to provide the first explicit constant for which the TS-DSR problem is PSPACE-complete, a question that was left open in the literature. From a parameterized complexity perspective, the token jumping variant of DSR, i.e., where tokens can jump to arbitrary vertices, is known to be FPT when parameterized by the size of the dominating sets on nowhere dense classes of graphs. But, in contrast, no non-trivial result was known about TS-DSR. We prove that DSR is actually much harder in the sliding model since it is XL-complete when restricted to bounded pathwidth graphs and even when parameterized by $k$ plus the feedback vertex set number of the graph. This gives, for the first time, a difference of behavior between the complexity under token sliding and token jumping for some problem on graphs of bounded treewidth. All our results are obtained using a brand new method, based on the hardness of the so-called Tape Reconfiguration problem, a problem we believe to be of independent interest.