Burton and Ozlen describe a kind of backtracking algorithm, which circumvents the complexity of the restricted vertex problem (nondeterministic polynomial-time (NP) complete). They use a domination test, which imposes a partial (but not total) order on the vectors that may define a vertex, and that have already satisfied quadrilateral constraints. Once a partial order is obtained through the domination test, constraints are defined, so that all possible combinations of zero and nonzero coordinates for the admissible vertices of the solution space are traversed in a depth-first manner. The authors use some other feasibility tests (based on certain type constraints and some defined matching equations) in order to prune the search tree so that the leaves at depth n correspond precisely to the admissible vertices of the solution space. In brief, the input is a 3-manifold triangulation, and the output is “all admissible vertices of the projective solution space.” No zero vector type belongs to the set of admissible vectors.

Their computational implementation allows for the use of native machine integers, such as 32-bit, 64-bit, and 128-bit integers. Also, since for each nonleaf node most children can be processed simultaneously, and since at each branch the data transfer has small polynomial size, we can use parallel and/or distributed computing. The algorithm supports incremental output, including early termination and progress tracking.

Finally, the authors show theoretical bounds and numerical experiments, where the tree traversal algorithm is several orders of magnitude better in time complexity (particularly for larger problems), and at worst the same in space complexity, when compared with the prior state of the art (the double description algorithm).

I strongly recommend this paper--the “full version” is available online (http://arxiv.org/abs/1010.6200/)--to applied knot mathematicians, and also to any mathematician who may want to substitute the authors’ implementations of the double description method for problems that require lengthy normal surface enumerations.