Article ID Journal Published Year Pages File Type
4650168 Discrete Mathematics 2009 7 Pages PDF
Abstract

We investigate the computational complexity of finding an element of a permutation group H⊆SnH⊆Sn with minimal distance to a given π∈Snπ∈Sn, for different metrics on SnSn. We assume that HH is given by a set of generators. In particular, the size of HH might be exponential in the input size, so that in general 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 HH is abelian of exponent two [R.G.E. Pinch, The distance of a permutation from a subgroup of SnSn, in: G. Brightwell, I. Leader, A. Scott, A. Thomason (Eds.), Combinatorics and Probability, Cambridge University Press, 2007, pp. 473–479]. We present a much simpler proof for this result, which also works for the Hamming Distance, the lplp distance, Lee’s Distance, Kendall’s tau, and Ulam’s Distance. Moreover, we give an NP-hardness proof for the l∞l∞ distance using a different reduction idea. Finally, we discuss the complexity of the corresponding fixed-parameter and maximization problems.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,