On the Congruency-Constrained Matroid Base

Consider a matroid where all elements are labeled with an element in \(\mathbb {Z}\) . We are interested in finding a base where the sum of the labels is congruent to \(g \pmod m\) . We show that this problem can be solved in \(\tilde{O}(2^{4m} n r^{5/6})\) time for a matroid with n elements and rank r, when m is either the product of two primes or a prime power. The algorithm can be generalized to all moduli and, in fact, to all abelian groups if a classic additive combinatorics conjecture by Schrijver and Seymour holds true. We also discuss the optimization version of the problem.