Algorithms for contractibility of compressed curves on 3-manifold boundaries

DOI10.1007/S00454-022-00411-XMaRDI QIDQ6174804zbMATH OpenOpenAlexWikidataFDO

Authors Erin W. Chambers, Francis Lazarus, Arnaud de Mesmay, Salman Parsa

Publication date 17 August 2023

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2012.02352

zbMATH Keywords

3-manifoldscompressed curvescomputational topologycontractibilitysurfaces

Mathematics Subject Classification ID

Fundamental group, presentations, free differential calculus (57M05) Discrete mathematics in relation to computer science (68R99)

Abstract: 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 $gamma$, and a collection of disjoint normal curves $Delta$, there is a polynomial-time algorithm to decide if $gamma$ lies in the normal subgroup generated by components of $Delta$ in the fundamental group of the surface after attaching the curves to a basepoint.

Recommendations

• Deciding contractibility of a non-simple curve on the boundary of a 3-manifold
• Transforming curves on surfaces
• scientific article; zbMATH DE number 7647903
• The computational complexity of basic decision problems in 3-dimensional topology
• Sphere recognition lies in NP

Cites work

• 0-efficient triangulations of 3-manifolds
• 3-manifold groups
• A new approach to crushing 3-manifold triangulations
• Affine structures in 3-manifolds. V: The triangulation theorem and Hauptvermutung
• Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization
• Algorithmic topology and classification of 3-manifolds
• Algorithms for the complete decomposition of a closed 3-manifold
• Bestimmung der Primfaktorzerlegung von Verkettungen
• Compressed decision problems in hyperbolic groups
• Computing Heegaard genus is NP-hard
• Counting intersections of normal curves
• Deciding contractibility of a non-simple curve on the boundary of a 3-manifold
• Decision problems for 3-manifolds and their fundamental groups
• Graphs on surfaces
• scientific article; zbMATH DE number 412172 (Why is no real title available?)
• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 1941341 (Why is no real title available?)
• scientific article; zbMATH DE number 1544074 (Why is no real title available?)
• scientific article; zbMATH DE number 2089992 (Why is no real title available?)
• scientific article; zbMATH DE number 2103273 (Why is no real title available?)
• scientific article; zbMATH DE number 2123636 (Why is no real title available?)
• scientific article; zbMATH DE number 7647903 (Why is no real title available?)
• On the complexity of braids.
• On the complexity of immersed normal surfaces
• Polynomial-time word problems.
• Simplifying triangulations
• Some conditionally hard problems on links and 3-manifolds
• The Compressed Word Problem for Groups
• The computational complexity of knot and link problems
• The computational complexity of knot genus and spanning area
• The efficient certification of knottedness and Thurston norm
• The size of spanning disks for polygonal curves
• The unbearable hardness of unknotting
• The word problem in fundamental groups of sufficiently large irreducible 3-manifolds
• Tracing compressed curves in triangulated surfaces
• Transforming curves on surfaces redux
• Word Problems and Membership Problems on Compressed Words

This page was built for publication: Algorithms for contractibility of compressed curves on 3-manifold boundaries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6174804)