Interesting Esoterica

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

Article by Richard G. E. Pinch
  • Published in 2005
  • Added on
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}
}