Universität zu Köln

Buchheim, Christoph ORCID: 0000-0001-9974-404X, Cameron, Peter J. and Wu, Taoyang (2009). On the Subgroup Distance Problem. Discrete Mathematics, 309 (4). pp. 962-968. Elsevier Science.

Preview

PDF zaik2006-529.pdf - Draft Version Download (123kB) | Preview

Abstract

We investigate the computational complexity of finding an element of a permutation group H subset S_n with a minimal distance to a given pi in S_n , for different metrics on S_n . We assume that H is given by a set of generators, such that the problem cannot be solved in polynomial time by exhaustive enumeration. For the case of the Cayley Distance, this problem has been shown to be NP-hard, even if H is abelian of exponent two Pinch, 2006. We present a much simpler proof for this result, which also works for the Hamming Distance, the l\_p distance, Lee's Distance, Kendall's tau, and Ulam's Distance. Moreover, we give an NP-hardness proof for the l\_oo distance using a different reduction idea. Finally, we settle the complexity of the corresponding fixed-parameter and maximization problems.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Buchheim, Christoph UNSPECIFIED orcid.org/0000-0001-9974-404X UNSPECIFIED Cameron, Peter J. UNSPECIFIED UNSPECIFIED UNSPECIFIED Wu, Taoyang UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-549036
Journal or Publication Title:	Discrete Mathematics
Volume:	309
Number:	4
Page Range:	pp. 962-968
Date:	2009
Publisher:	Elsevier Science
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/54903