Bounded-Support Additive Latin Transversals

Abstract

We consider the following additive Latin transversal problem. Given a multiset $A=(a_1,\dots ,a_k)$ of elements of ${\mathbb{Z}}_m$ and a set $B\subseteq {\mathbb{Z}}_m$ of cardinality $k$, the task is to order $B$ as $b_1,\dots ,b_k$ so that the sums $a_i+b_i$ are pairwise distinct. When $k=m$, Hall proved that a solution exists if and only if ${\sum }_{i=1}^m{a}_i\equiv 0(\mathrm{mod}m)$; moreover, his theorem yields a polynomial-time construction. Alon proved that a solution always exists when $m$ is prime and $k<m$, but no polynomial-time construction is known in general. Our main algorithmic contribution is a direct randomized algorithm for Color-Counted Matching: given an edge-colored graph and prescribed target counts for the colors, find a matching using exactly the prescribed number of edges of each color. If $q$ is the sum of the target counts and $h$ is the number of colors, our base-$(q+1)$ reduction to Exact Red Matching, combined with the algorithm of Mulmuley-Vazirani-Vazirani, gives a randomized algorithm with running time ${\left(|V{|}^2+|E|(q+1{)}^{h-1}\right)}^{O(1)}$ for an input graph $(V,E)$. Thus the dependence on the target matching size is $q^{O(h)}$, up to polynomial factors in the graph size. In contrast, applying the general matching-ILP theorem of Lassota and Ligthart as a black box yields a $q^{O(h^2)}$ dependence for the corresponding fixed-size color-counted instances. Applying this primitive to additive Latin transversals with $s=|\mathrm{supp}(A)|$, we obtain an algorithm in randomized time $(k+\log m{)}^{O(s)}$. In particular, additive Latin transversals are randomized polynomial-time constructible for every fixed support size.

Topics & keywords