The distance of a permutation from a subgroup of S_n

2005/11/20 by Richard G. E. Pinch, Pinch, Richard G. E.
Mathematics · #05C38 #20B35 #20B40 #68Q25 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C38 #msc:20B35 #msc:20B40 #msc:68Q25

paper · pdf · doi:10.48550/arxiv.math/0511501

6 pages, 5 figures

arxiv created 2005/11/20 · arxiv updated 2009/12/01

Abstract

We show that the problem of computing the distance of a given permutation from a subgroup H of S_n is in general NP-complete, even under the restriction that H is elementary Abelian of exponent 2. The problem is shown to be polynomial-time equivalent to a problem related to finding a maximal partition of the edges of an Eulerian directed graph into cycles and this problem is in turn equivalent to the standard NP-complete problem of Boolean satisfiability.

Related

• On the Subgroup Distance Problem in Cyclic Permutation Groups
• Permutations that separate close elements
• Distance in the Ellipticity Graph
• Metrics on Permutation Families Defined by a Restriction Graph
• Partition distances