Rok Požar (IMFM, Slovenija): Algorithmic and complexity aspects of lifting automorphisms

Povzetek: Let $a_1,a_2,\ldots, a_r$ and $b_1,b_2,\ldots, b_r$ be permutations from the symmetric group $S_n$. Is there a permutation $\tau \in S_n$ such that $b_j = \tau^{-1}\,a_j\,\tau $, for all indices $j$? We provide an algorithm, which either finds that no such a permutation $\tau$ exists or else construct all of them in time $\CO{(r\, n^2)}$. As an application, the test whether a given automorphism of a connected graph lifts along a given connected covering projection can be done in time $\CO{(r\, n^2)}$, where $r$ is the Betti number of the graph.