\(\mathcal{NP}\)-completeness of generalized multi-Skolem sequences (Q2384390)

A generalized multi-Skolem pair is a pair \((P, A)\), where \(P\) is a set of positions and \(A\) is a multiset of positive integers, such that the positions in \(P\) can be partitioned into the differences in \(A\). For example, \((\{ 1,2,4,5,7,8\}, \{ 1,6,6\})\) is a generalized multi-Skolem pair, because \(\{ 5-4, 7-1, 8-2\} = \{ 1, 6, 6\}\). This paper proves that the problem of deciding which pairs \((P, A)\) are generalized multi-Skolem pairs is NP-complete.