Markus Lohrey ; Andreas Rosowski - Parameterized Complexity of Factorization Problems

dmtcs:13087 - Discrete Mathematics & Theoretical Computer Science, September 20, 2025, vol. 27:3 - https://doi.org/10.46298/dmtcs.13087
Parameterized Complexity of Factorization ProblemsArticle

Authors: Markus Lohrey ; Andreas Rosowski

    We study the parameterized complexity of the following factorization problem: given elements $a,a_1, \ldots, a_m$ of a monoid and a parameter $k$, can $a$ be written as the product of at most (or exactly) $k$ elements from $a_1, \ldots, a_m$. Several new upper bounds and fpt-equivalences with more restricted problems (subset sum and knapsack) are shown. Finally, some new upper bounds for variants of the parameterized change-making problems are shown.


    Volume: vol. 27:3
    Section: Discrete Algorithms
    Published on: September 20, 2025
    Accepted on: August 18, 2025
    Submitted on: February 20, 2024
    Keywords: Group Theory, 20B05, 20F10, 68Q45

    Consultation statistics

    This page has been seen 249 times.
    This article's PDF has been downloaded 635 times.