Reconfiguring (non-spanning) arborescences
Reconfiguring (non-spanning) arborescences
复制标题
重新配置（非跨越）树状结构
DOI：
10.1016/j.tcs.2022.12.007
复制
发表时间：
2023
影响因子：
1.1
通讯作者：
Kunihiro Wasa
中科院分区：
文献类型：
--
作者：
Takehiro Ito;Yuni Iwamasa;Yasuaki Kobayashi;Yu Nakahata;Yota Otachi;Kunihiro Wasa
本文研究了有向图中子图重构问题的计算复杂性。更具体地说，我们专注于在有向图，树是一个有向图，使其底层的无向图形成一棵树，所有的顶点有在度最多为1的重构树形图的问题。给定有向图中的两个树形图，问题的目标是确定在给定的树形图之间是否存在树形图的（重构）序列，使得序列中的每个树形图可以通过移除一个弧然后添加另一个弧从前一个树形图获得。我们表明，这个问题可以在多项式时间内解决，而这个问题是PSPACE-完全的，当我们限制在一个重新配置序列的有向路径或放松有向无环图的树形结构。我们还表明，有一个多项式时间的算法，找到一个最短的重构序列之间的两个生成树形。
In this paper, we investigate the computational complexity of subgraph reconfiguration problems in directed graphs. More specifically, we focus on the problem of reconfiguring arborescences in a digraph, where an arborescence is a directed graph such that its underlying undirected graph forms a tree and all vertices have in-degree at most 1. Given two arborescences in a digraph, the goal of the problem is to determine whether there is a (reconfiguration) sequence of arborescences between the given arborescences such that each arborescence in the sequence can be obtained from the previous one by removing an arc and then adding another arc. We show that this problem can be solved in polynomial time, whereas the problem is PSPACE-complete when we restrict arborescences in a reconfiguration sequence to directed paths or relax to directed acyclic graphs. We also show that there is a polynomial-time algorithm for finding a shortest reconfiguration sequence between two spanning arborescences.