On the Subgroup Distance Problem

Buchheim, Christoph and Cameron, Peter J. and Wu, Taoyang (2009) On the Subgroup Distance Problem.
Published in: Discrete Mathematics Vol. 309 (4). pp. 962-968.


We investigate the computational complexity of finding an element of a permutation group H subset 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 [Pinch, 2006]. 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_oo distance using a different reduction idea. Finally, we settle the complexity of the corresponding fixed-parameter and maximization problems.

Download: [img] PDF - Preprinted Version
Download (123kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2006-529
Depositing User: Christoph Buchheim
Date Deposited: 22 Jan 2008 00:00
Last Modified: 09 Jan 2012 15:42
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/529