On Computing Sets of Integers with Maximum Number of Pairs Summing to Powers of 2

We address the problem of finding sets of integers of a given size with the maximum number of pairs summing to powers of 2. By fixing particular pairs, this problem reduces to finding a labeling of the vertices of a given graph with pairwise distinct integers such that the endpoint labels for each edge sum to a power of 2. We propose an efficient algorithm for this problem, which at its core relies on another algorithm that, given two sets of linear homogeneous polynomials with integer coefficients, computes all variable assignments to powers of 2 that nullify all polynomials from the first set but neither one from the second. With the proposed algorithms, we determine the maximum size of graphs of order n that admit such a labeling for all \(n\le 20\) . We also identify the minimal forbidden subgraphs of order \(\le 11\) , whose presence prevents the graphs from having such a labeling.