论文标题
在3个manifold边界上压缩曲线合约的算法
Algorithms for Contractibility of Compressed Curves on 3-Manifold Boundaries
论文作者
论文摘要
在本文中，我们证明了在3个manifold的边界上确定任意封闭曲线合同的问题是NP。我们强调的是，歧管和曲线都是问题的输入。此外，如果将曲线作为压缩单词给出，我们的算法也有效。以前，这种算法以简单（非压缩的）曲线而闻名，在非常有限的情况下，对于具有自我交流的曲线。此外，我们的算法是在输入3 manifold的复杂性中固定参数。 作为证据的一部分，我们获得了在表面上压缩曲线的新多项式算法，我们认为这具有独立的兴趣。我们提供了一种多项式时间算法，在表面上给定一个可定向的表面和压缩环，将循环的规范形式计算为压缩词。特别是，可以在多项式时间内决定压缩曲线的合同。事先发表的工作仅考虑恒定属表面。更一般地，我们在多项式时间内解决了以下正常的亚组成员资格问题：鉴于可任意定向的表面，闭合曲线$γ$以及一系列差异的正常曲线$δ$，有多项式时间算法可以决定$γ$是否在$Δ$ cultement cul ne cultement cul ne nefers culters culters in Culted nefers cultimal culters中是否存在。
In this paper we prove that the problem of deciding contractibility of an arbitrary closed curve on the boundary of a 3-manifold is in NP. We emphasize that the manifold and the curve are both inputs to the problem. Moreover, our algorithm also works if the curve is given as a compressed word. Previously, such an algorithm was known for simple (non-compressed) curves, and, in very limited cases, for curves with self-intersections. Furthermore, our algorithm is fixed-parameter tractable in the complexity of the input 3-manifold. As part of our proof, we obtain new polynomial-time algorithms for compressed curves on surfaces, which we believe are of independent interest. We provide a polynomial-time algorithm which, given an orientable surface and a compressed loop on the surface, computes a canonical form for the loop as a compressed word. In particular, contractibility of compressed curves on surfaces can be decided in polynomial time; prior published work considered only constant genus surfaces. More generally, we solve the following normal subgroup membership problem in polynomial time: given an arbitrary orientable surface, a compressed closed curve $γ$, and a collection of disjoint normal curves $Δ$, there is a polynomial-time algorithm to decide if $γ$ lies in the normal subgroup generated by components of $Δ$ in the fundamental group of the surface after attaching the curves to a basepoint.
