Reconfiguration over Tree Decompositions
Reconfiguration over Tree Decompositions
复制标题
树分解的重新配置
DOI：
10.1007/978-3-319-13524-3_21
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Marcin Wrochna
中科院分区：
文献类型：
--
作者：
A. E. Mouawad;N. Nishimura;Venkatesh Raman;Marcin Wrochna
顶点子集图问题定义输入图的哪些顶点子集是可行解。顶点子集问题的重构版本掩盖了是否可能在最多的步骤中将一个可行解转换为另一个可行解，其中每一步都是一个顶点的添加或删除，并且每个中间集也是一个大小为的可行解。基于最近的结果，我们建立了参数化的大多数顶点子集问题的重构版本的W[1]-硬度，我们研究了这类问题的复杂性，这些问题被限制在有界树宽的图中。我们证明了大多数顶点子集问题的重构版本在最多树宽的图上保持pspace完全，但对于所有在单进二阶逻辑（MSOL）中可定义的顶点子集问题都是固定参数可处理的参数化的。为了证明后一种结果，我们引入了一种技术，该技术允许我们绕过基数约束并定义MSOL中的重新配置问题。
A vertex-subset graph problemQdefines which subsets of the vertices of an input graph are feasible solutions. The reconfiguration version of a vertex-subset problemasks whether it is possible to transform one feasible solution forinto another in at moststeps, where each step is a vertex addition or deletion, and each intermediate set is also a feasible solution forof size bounded by. Motivated by recent results establishing W[1]-hardness of the reconfiguration versions of most vertex-subset problems parameterized by, we investigate the complexity of such problems restricted to graphs of bounded treewidth. We show that the reconfiguration versions of most vertex-subset problems remain PSPACE-complete on graphs of treewidth at mostbut are fixed-parameter tractable parameterized byfor all vertex-subset problems definable in monadic second-order logic (MSOL). To prove the latter result, we introduce a technique which allows us to circumvent cardinality constraints and define reconfiguration problems in MSOL.