In this paper, we investigate the computational complexity of subgraph reconfiguration problems in directed graphs. More specifically, we focus on the problem of determining whether, given two directed trees in a digraph, there is a (reconfiguration) sequence of directed trees such that for every pair of two consecutive trees in the sequence, one of them is obtained from the other 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 directed trees in a reconfiguration sequence to form directed paths. We also show that there is a polynomial-time algorithm for finding a shortest reconfiguration sequence between two directed spanning trees.


翻译:在本文中,我们调查了定向图表中子图重新配置问题的计算复杂性。更具体地说,我们侧重于确定,如果在一份图表中给出两棵直线树,是否有(重新配置)直线树序列,这样,每对连续两棵树的序列中,每对直线树中的一对通过去除弧从另一对树中获取,然后增加另一根弧。我们表明,这个问题可以在多元时间中解决,而当我们按照重组序列将定向树限制在形成定向路径的顺序中时,问题就是PSPACE已经完成。我们还表明,在两棵直线横贯的树之间,有一个多元时算法,可以找到最短的重组序列。

0
下载
关闭预览

相关内容

专知会员服务
27+阅读 · 2021年7月3日
FlowQA: Grasping Flow in History for Conversational Machine Comprehension
专知会员服务
28+阅读 · 2019年10月18日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
spinningup.openai 强化学习资源完整
CreateAMind
6+阅读 · 2018年12月17日
计算机类 | 期刊专刊截稿信息9条
Call4Papers
4+阅读 · 2018年1月26日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
15+阅读 · 2017年11月16日
Arxiv
0+阅读 · 2021年9月8日
Arxiv
0+阅读 · 2021年9月8日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
相关资讯
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
spinningup.openai 强化学习资源完整
CreateAMind
6+阅读 · 2018年12月17日
计算机类 | 期刊专刊截稿信息9条
Call4Papers
4+阅读 · 2018年1月26日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
15+阅读 · 2017年11月16日
相关论文
Top
微信扫码咨询专知VIP会员