Factorizing the Brauer monoid in polynomial time

Finding a minimal factorization for a generic semigroup can be done by using the Froidure-Pin Algorithm, which is not feasible for semigroups of large sizes. On the other hand, if we restrict our attention to just a particular semigroup, we could leverage its structure to obtain a much faster algorithm. In particular, $\mathcal{O}(N^2)$ algorithms are known for factorizing the Symmetric group $S_N$ and the Temperley-Lieb monoid $\mathcal{T}{\mathcal{L}}_N$, but none for their superset the Brauer monoid ${\mathcal{B}}_N$. In this paper we hence propose a $\mathcal{O}(N^4)$ factorization algorithm for ${\mathcal{B}}_N$. At each iteration, the algorithm rewrites the input $X\in {\mathcal{B}}_N$ as $X=X^{\mathrm{\prime }}\circ p_i$ such that $\mathrm{\ell }(X^{\mathrm{\prime }})=\mathrm{\ell }(X)-1$, where $p_i$ is a factor for $X$ and $\mathrm{\ell }$ is a length function that returns the minimal number of factors needed to generate $X$.