Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-146 | 30th September 2006 00:00

On the Subgroup Distance Problem

RSS-Feed




TR06-146
Authors: Christoph Buchheim, Peter J Cameron, Taoyang Wu
Publication: 1st December 2006 22:13
Downloads: 3714
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint