Recognizing trace graphs of closed braids (Q624256)

Motivated by the problem of finding an algorithm determining whether two braids are conjugate and running in polynomial time (in the length of the braid), the authors show that the problem is equivalent to determining whether two graphs of a special type are related by a finite sequence of two types of moves, called \textsl{trihedral} and \textsl{tetrahedral}. To translate the group theoretical problem on braids into a combinatorial one on graphs, the authors start by observing that two braids are isotopic if and only if the corresponding closed braids are isotopic in the solid torus that contains them. A \textsl{\(1\)-parameter approach} is then applied to distinguish the closed braids. The \textsl{\(1\)-parameter approach} for links in a solid torus was originally introduced by Fiedler and then exploited the authors [J. Math. Soc. Japan 62, 167--211 (2010; Zbl 1201.57003)] to study the isotopy problem for links in a solid torus. The idea behind it is to consider a \(1\)-parameter family of diagrams associated to the link obtained as projections of the link into a sectional annulus of the solid torus when the annulus makes a \(2\pi\) turn around the solid torus core. To this family of diagrams the authors associate a \textsl{trace graph}, i.e. the graph in a thickened torus determined by the crossings of the family of diagrams, plus some labelling (roughly taking into account which strands the braid are crossing and which is above). It turns out that that the isotopy problem for links in a solid torus is equivalent to a combinatorial problem for the graphs. The main result of the paper states that there is an algorithm to decide whether two trace graphs, associated to braids on \(n\) strands of length at most \(\ell\), are related by a finite sequence of trihedral moves, and the complexity of the algorithm is polynomial in \(\ell\) and \(n\). Since tetrahedral moves can never appear for trace graphs associated to closures of \(3\)-braids, the main result implies that there is a polynomial algorithm that solves the conjugacy problem for the braid group on \(3\) strands.