Reconfiguration in bounded bandwidth and tree-depth
作者：
Highlights：
• The complexity of finding paths between solutions to graph problems is studied.
• We show PSPACE-completeness in bounded bandwidth (hence pathwidth and treewidth).
• Turing Machine computations are reduced to a very limited string rewriting system.
• This gives a simple word problem from which many further reductions follow easily.
• Complexity of homomorphism reconfiguration is tightly characterized by tree-depth.
摘要
•The complexity of finding paths between solutions to graph problems is studied.•We show PSPACE-completeness in bounded bandwidth (hence pathwidth and treewidth).•Turing Machine computations are reduced to a very limited string rewriting system.•This gives a simple word problem from which many further reductions follow easily.•Complexity of homomorphism reconfiguration is tightly characterized by tree-depth.
论文关键词：Reconfiguration,Recoloring,Treewidth,Bandwidth,Tree-depth,Graph homomorphism
论文评审过程：Received 23 August 2016, Revised 8 September 2017, Accepted 21 November 2017, Available online 5 December 2017, Version of Record 13 December 2017.
论文官网地址：https://doi.org/10.1016/j.jcss.2017.11.003
