Reconfiguration in bounded bandwidth and tree-depth
Reconfiguration in bounded bandwidth and tree-depth
复制标题
有限带宽和树深度的重新配置
DOI：
10.1016/j.jcss.2017.11.003
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Marcin Wrochna
中科院分区：
文献类型：
--
作者：
Marcin Wrochna
我们证明了几个已知的PSPACE-complete重构问题即使被限制在有限带宽（路径宽度和树宽度）的图中仍然如此。关键的一步是注意到与非常有限的字符串重写系统的相似性，其直接模拟图灵机的能力是众所周知的。另一方面，我们证明了一大类自然重构问题（来自图同态）在有界树深度的图上变得可处理，并证明了一个二分类，表明这在某种意义上是紧密的。
We show that several reconfiguration problems known to be PSPACE-complete remain so even when limited to graphs of bounded bandwidth (and hence pathwidth and treewidth). The essential step is noticing the similarity to very limited string rewriting systems, whose ability to directly simulate Turing Machines is classically known. On the other hand, we show that a large class of natural reconfiguration problems (coming from graph homomorphisms) becomes tractable on graphs of bounded tree-depth, and prove a dichotomy showing this to be in some sense tight.