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. 962968.
Abstract
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 NPhard, 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 NPhardness proof for the l_oo distance using a different reduction idea. Finally, we settle the complexity of the corresponding fixedparameter and maximization problems.
Download: 
PDF
 Preprinted Version
Download (123kB)  Preview 

Export as:  [error in script] 
Editorial actions:  View Item (Login required) 
Item Type:  Article 

Citations:  [error in script] 5 (Google Scholar)  [error in script] 
Uncontrolled Keywords:  [error in script] 
Subjects: 

Uncontrolled Keywords:  permutation groups, subgroup distance 
Subjects:  20XX Group theory and generalizations > 20Bxx Permutation groups > 20B40 Computational methods 68XX Computer science > 68Qxx Theory of computing > 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 
Divisions:  Institute of Computer Science > Computer Science Department  Prof. Dr. Juenger 
Depositing User:  Christoph Buchheim 
Date Deposited:  22 Jan 2008 00:00 
Last Modified:  09 Jan 2012 15:42 
ZAIK Number:  [error in script] 

Depositing User:  Christoph Buchheim 
Date Deposited:  22 Jan 2008 00:00 
Last Modified:  09 Jan 2012 15:42 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/529 