3 papers
math.GR2026
On the Subgroup Distance Problem in Cyclic Permutation Groups
Andreas Rosowski
We show that the Subgroup distance problem regarding the Hamming distance, the Cayley distance and the distance is NP-complete when the input group is cyclic. When we re…
math.GR2025
Parameterized Complexity of Factorization Problems
Markus Lohrey, Andreas Rosowski
We study the parameterized complexity of the following factorization problem: given elements of a monoid and a parameter , can be written as the product…
math.GR2025
Finding cycle types in permutation groups with few generators
Markus Lohrey, Andreas Rosowski
The problem whether a given permutation group contains a permutation with a given cycle type is studied. This problem is known to be NP-complete. In this paper it is shown that the…