A Faster Algorithm for Pigeonhole Equal Sums

Abstract

An important area of research in exact algorithms is to solve Subset-Sum-type problems faster than meet-in-middle. In this paper we study Pigeonhole Equal Sums, a total search problem proposed by Papadimitriou (1994): given $n$ positive integers $w_1,\dots ,w_n$ of total sum ${\sum }_{i=1}^n{w}_i<2^n-1$, the task is to find two distinct subsets $A,B\subseteq [n]$ such that ${\sum }_{i\in A}{w}_i={\sum }_{i\in B}{w}_i$. Similar to the status of the Subset Sum problem, the best known algorithm for Pigeonhole Equal Sums runs in $O^{\ast }(2^{n/2})$ time, via either meet-in-middle or dynamic programming (Allcock, Hamoudi, Joux, Klingelhöfer, and Santha, 2022). Our main result is an improved algorithm for Pigeonhole Equal Sums in $O^{\ast }(2^{0.4n})$ time. We also give a polynomial-space algorithm in $O^{\ast }(2^{0.75n})$ time. Unlike many previous works in this area, our approach does not use the representation method, but rather exploits a simple structural characterization of input instances with few solutions.

11 pages