On the Fine-Grained Complexity of the Unbounded SubsetSum and the Frobenius Problem
Kim-Manuel Klein · Society for Industrial and Applied Mathematics eBooks · 2022
Consider positive integral solutions to the equation a0x0 + … + anxn = t. In the so called unbounded subset sum problem, the objective is to decide whether such a solution exists, whereas in the Frobenius problem, the objective is to compute the largest t such that there is no such solution. In this paper we study the algorithmic complexity of the unbounded subset sum, the Frobenius problem and a generalization of both problems. More precisely, we study pseudo-polynomial time algorithms with a running time that depends on the smallest number a0 or respectively the largest number an. For the parameter a0, we show that all considered problems are subquadratically equivalent to (min, +)-convolution, a fundamental algorithmic problem from the area of fine-grained complexity. By this equivalence, we obtain hardness results for the considered problems (based on the assumption that an algorithm with a subquadratic running time for (min, +)-convolution does not exist) as well as algorithms with improved running time. The proof for the equivalence makes use of structural properties of solutions, a technique that was developed in the area of integer programming. In case of the complexity of the problems parameterized by an, we present improved algorithms. For example we give a quasi linear time algorithm for the Frobenius problem as well as a hardness result based on the strong exponential time hypothesis.