The complexity of dominating set reconfiguration
The complexity of dominating set reconfiguration
复制标题
DOI：
10.1016/j.tcs.2016.08.016
复制
发表时间：
2016-10-25
影响因子：
1.1
通讯作者：
Tebbal, Youcef
中科院分区：
文献类型：
--
作者：
Haddadan, Arash;Ito, Takehiro;Tebbal, Youcef
假设给定一个图G的两个控制集D-S和D-t，它们的基数至多是给定的阈值k，然后我们被问到在D-S和Dt之间是否存在一个G的控制集序列，使得该序列中的每个控制集至多有k个基数，并且可以从前一个控制集通过增加或删除恰好一个顶点来获得。这个决策问题通常被称为PSPACE-完全问题。本文从图类的角度研究了这一问题的复杂性。我们首先证明了即使对于平面图、有界带宽图、分裂图和二部图，问题仍然是PSPACE-完全的。然后，我们给出了构造线性时间算法的一般方案，并证明了对于余图、森林和区间图，该问题可以在线性时间内求解。此外，对于这些容易处理的情况，如果存在期望的序列，使得添加和删除的数目由O(N)有界，则我们可以得到期望的序列，其中n是输入图中的顶点数。(C)2016爱思唯尔B.V.保留所有权利。
Suppose that we are given two dominating sets D-s and D-t of a graph G whose cardinalities are at most a given threshold k. Then, we are asked whether there exists a sequence of dominating sets of G between D-s, and Dt such that each dominating set in the sequence is of cardinality at most k and can be obtained from the previous one by either adding or deleting exactly one vertex. This decision problem is known to be PSPACE-complete in general. In this paper, we study the complexity of this problem from the viewpoint of graph classes. We first prove that the problem remains PSPACE-complete even for planar graphs, bounded bandwidth graphs, split graphs, and bipartite graphs. We then give a general scheme to construct linear-time algorithms and show that the problem can be solved in linear time for cographs, forests, and interval graphs. Furthermore, for these tractable cases, we can obtain a desired sequence if it exists such that the number of additions and deletions is bounded by O(n), where n is the number of vertices in the input graph. (C) 2016 Elsevier B.V. All rights reserved.