Reconfiguration on sparse graphs
Reconfiguration on sparse graphs
复制标题
DOI：
10.1016/j.jcss.2018.02.004
复制
发表时间：
2018-08-01
影响因子：
1.1
通讯作者：
Saurabh, Saket
中科院分区：
文献类型：
--
作者：
Lokshtanov, Daniel;Mouawad, Amer E.;Saurabh, Saket
顶点子集图问题Q定义了输入图的哪些顶点子集是可行解。一个顶点子集问题的重构变体要求，给定两个大小为k的可行解，是否可能通过一系列顶点的添加/删除将一个转换为另一个，使得每个中间集仍然是大小以k为界的可行解。我们研究了两个经典顶点子集问题的重构变体，即独立集和支配集。我们用ISR表示前者，用DSR表示后者。ISR和DSR在有界带宽和w[1]的图上都是pspace完全的。在一般图上很难用k参数化。我们证明了当输入图是有界退化或无处密集时，ISR是由k参数化的固定参数可处理的。对于DSR，当输入图不包含大的曲线时，我们展示了用k参数化的固定参数可处理问题。(C) 2018爱思唯尔公司版权所有。
A vertex-subset graph problem Q defines which subsets of the vertices of an input graph are feasible solutions. A reconfiguration variant of a vertex-subset problem asks, given two feasible solutions of size k, whether it is possible to transform one into the other by a sequence of vertex additions/deletions such that each intermediate set remains a feasible solution of size bounded by k. We study reconfiguration variants of two classical vertex subset problems, namely INDEPENDENT SET and DOMINATING SET. We denote the former by ISR and the latter by DSR. Both ISR and DSR are PSPACE-complete on graphs of bounded bandwidth and w [1.]-hard parameterized by k on general graphs. We show that ISR is fixed-parameter tractable parameterized by k when the input graph is of bounded degeneracy or nowhere dense. For DSR, we show the problem fixed-parameter tractable parameterized by k when the input graph does not contain large bicliques. (C) 2018 Elsevier Inc. All rights reserved.