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

• Published in 2005
• Added on 2020-04-30

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

• http://arxiv.org/abs/math/0511501v1
• http://arxiv.org/pdf/math/0511501v1

Other information

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-09-26},
	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}
}