# The distance of a permutation from a subgroup of $S_n$

• Published in 2005
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.

### BibTeX entry

@article{ThedistanceofapermutationfromasubgroupofSn,
title = {The distance of a permutation from a subgroup of $S{\_}n$},
author = {Richard G. E. Pinch},
url = {http://arxiv.org/abs/math/0511501v1 http://arxiv.org/pdf/math/0511501v1},
urldate = {2020-04-30},
year = 2005,
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.},
comment = {},
archivePrefix = {arXiv},
eprint = {math/0511501},
primaryClass = {math.CO},
collections = {basically-computer-science,computational-complexity-of-games,the-groups-group}
}