The most classic polynomial algorithm is Eppstein's one [1]}.
It works in \(\mathcal {O}(n^3 + k n^2)\)  time and finds a reset word of length at most \((n^3-n)/3\)  (due to the Frankl-Pin's bound).
Several heuristic improvements were proposed, e.g., Cycle, SynchroP, and SynchroPL algorithms [2]}, [3]}, which do not improve guarantees but behave better in experimental settings, even at the cost of increased worst-case time complexity.
Recent works also involve attempts to speed-up heuristics by adapting to parallel and GPU computation [4]}, [5]}.
