TR06-146 Authors: Christoph Buchheim, Peter J Cameron, Taoyang Wu

Publication: 1st December 2006 22:13

Downloads: 1809

Keywords:

We investigate the computational complexity of finding an element of

a permutation group~$H\subseteq S_n$ with a minimal distance to a

given~$\pi\in S_n$, for different metrics on~$S_n$. We assume

that~$H$ is given by a set of generators, such that the problem

cannot be solved in polynomial time by exhaustive enumeration. For

the case of the Cayley Distance, this problem has been shown to be

NP-hard, even if~$H$ is abelian of exponent two~\cite{pinch06}. We

present a much simpler proof for this result, which also works for

the Hamming Distance, the $l_p$ distance, Lee's Distance, Kendall's

tau, and Ulam's Distance. Moreover, we give an NP-hardness proof

for the $l_\infty$ distance using a different reduction idea.

Finally, we settle the complexity of the corresponding

fixed-parameter and maximization problems.