# 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

## Other information

- key
- ThedistanceofapermutationfromasubgroupofSn
- type
- article
- date_added
- 2020-04-30
- date_published
- 2005-05-24

### BibTeX entry

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