Finding the smallest $d$-chain with a specific $(d-1)$-boundary in a simplicial complex is known as the \textsc{Minimum Bounded Chain} (MBC$_d$) problem. The MBC$_d$ problem is NP-hard for all $d\geq 2$. In this paper, we prove that it is also W[1]-hard for all $d\geq 2$, if we parameterize the problem by solution size. We also give an algorithm solving the MBC$_1$ problem in polynomial time and introduce and implemented two fixed parameter tractable (FPT) algorithms solving the MBC$_d$ problem for all $d$. The first algorithm is a generalized version of Dijkstra's algorithm and is parameterized by solution size and coface degree. The second algorithm is a dynamic programming approach based on treewidth, which has the same runtime as a lower bound we prove under the exponential time hypothesis.


翻译:在简单复合物中找到一个特定美元(d-1)美元边界线的最小的美元链,称为 \ textsc{ minBounded chail} (MBC$_d$) 问题。 MBC$_d$问题是所有$d\geq 2$的硬NP。在本文中,我们证明,如果我们用解决方案大小来参数化问题,那么所有$d\geq 2$也是W[1]-hard。我们还给出一个算法,在多元时间内解决MBC$_1美元的问题,并引入和实施两种固定参数可移动的算法(FPT),解决所有美元 MBC$_d$的问题。第一个算法是Dijkstra的算法的通用版本,并按解算法大小和共同面度进行参数比较。第二个算法是一种动态的编程方法,以树线线为基础,其运行时间与我们在指数时间假设下证明的较低约束时间相同。

0
下载
关闭预览

相关内容

【Manning新书】C++并行实战,592页pdf,C++ Concurrency in Action
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
25+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
Arxiv
0+阅读 · 2021年10月11日
Arxiv
0+阅读 · 2021年10月10日
VIP会员
相关VIP内容
【Manning新书】C++并行实战,592页pdf,C++ Concurrency in Action
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
25+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
Top
微信扫码咨询专知VIP会员