A Tree Traversal Algorithm for Decision Problems in Knot Theory and 3-Manifold Topology
- PDF / 1,002,253 Bytes
- 30 Pages / 439.37 x 666.142 pts Page_size
- 60 Downloads / 153 Views
A Tree Traversal Algorithm for Decision Problems in Knot Theory and 3-Manifold Topology Benjamin A. Burton · Melih Ozlen
Received: 29 October 2010 / Accepted: 26 March 2012 / Published online: 12 May 2012 © Springer Science+Business Media, LLC 2012
Abstract In low-dimensional topology, many important decision algorithms are based on normal surface enumeration, which is a form of vertex enumeration over a high-dimensional and highly degenerate polytope. Because this enumeration is subject to extra combinatorial constraints, the only practical algorithms to date have been variants of the classical double description method. In this paper we present the first practical normal surface enumeration algorithm that breaks out of the double description paradigm. This new algorithm is based on a tree traversal with feasibility and domination tests, and it enjoys a number of advantages over the double description method: incremental output, significantly lower time and space complexity, and a natural suitability for parallelisation. Experimental comparisons of running times are included. Keywords Normal surfaces · Vertex enumeration · Tree traversal · Backtracking · Linear programming Mathematics Subject Classification Primary 57N10 · 52B55 · Secondary 90C05 · 57N35 1 Introduction Much research in low-dimensional topology has been driven by decision problems. Examples from knot theory include unknot recognition (given a polygonal repreB.A. Burton () School of Mathematics and Physics, The University of Queensland, Brisbane, QLD 4072, Australia e-mail: [email protected] M. Ozlen School of Mathematical and Geospatial Sciences, RMIT University, GPO Box 2476V, Melbourne, VIC 3001, Australia e-mail: [email protected]
Algorithmica (2013) 65:772–801
773
sentation of a knot, decide whether it is equivalent to a trivial unknotted loop), and the more general problem of knot equivalence (given two polygonal representations of knots, decide whether they are equivalent to each other). Analogous examples from 3-manifold topology include 3-sphere recognition (given a triangulation of a 3manifold, decide whether this 3-manifold is the 3-dimensional sphere), and the more general homeomorphism problem (given two triangulations of 3-manifolds, decide whether these 3-manifolds are homeomorphic, i.e., “topologically equivalent”). Significant progress has been made on these problems over the past 50 years. For instance, Haken introduced an algorithm for recognising the unknot in the 1960s [22], and Rubinstein presented the first 3-sphere recognition algorithm in the early 1990s [35]. Since Perelman’s recent proof of the geometrisation conjecture [29], we now have a complete (but extremely complex) algorithm for the homeomorphism problem, pieced together though a diverse array of techniques by many different authors [25, 31]. A key problem remains with many 3-dimensional decision algorithms (including all of those mentioned above): the best known algorithms run in exponential time (and for some problems, worse), where the input size is
Data Loading...
