2 citations · 2 across the 4 of their papers we have counts for
4 papers · 1 filter
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…
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…
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…
Membership Problems in Finite Groups
Markus Lohrey, Andreas Rosowski, Georg Zetzsche
We show that the subset sum problem, the knapsack problem and the rational subset membership problem for permutation groups are NP-complete. Concerning the knapsack problem we obta…