论文标题
同源性通过参数化复杂性理论的镜头本地化
Homology Localization Through the Looking-Glass of Parameterized Complexity Theory
论文作者
论文摘要
找到代表简单复合物中同源类别的最低权重的循环被称为同源性定位（HL）。在这里，我们使用参数化的复杂性理论解决了这个NP完整问题。我们表明，当解决方案大小参数化时，近似HL问题是W [1] - hard。我们还基于树宽解决了FPT时间的HL问题，设计并实现了两种算法。两种算法都是道德联系，但我们的结果表明，在实践中，一个算法表现出色。
Finding a cycle of lowest weight that represents a homology class in a simplicial complex is known as homology localization (HL). Here we address this NP-complete problem using parameterized complexity theory. We show that it is W[1]-hard to approximate the HL problem when it is parameterized by solution size. We have also designed and implemented two algorithms based on treewidth solving the HL problem in FPT-time. Both algorithms are ETH-tight but our results shows that one outperforms the other in practice.
