# The distance of a permutation from a subgroup of \(S_n\)

- Published in 2005
- Added on

In the collections

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.

## Links

### 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} }