{"ID":6537754,"CreatedAt":"2026-07-14T02:54:43.516908796Z","UpdatedAt":"2026-07-15T03:28:55.185153975Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.11241","arxiv_id":"2607.11241","title":"Bounded-Support Additive Latin Transversals via Color-Counted Matching","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 \\pmod m$; moreover, his theorem yields a polynomial-time construction. Alon proved that a solution always exists when $m$ is prime and $k\u003cm$, 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=|\\operatorname{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.","short_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 exis...","url_abs":"https://arxiv.org/abs/2607.11241","url_pdf":"https://arxiv.org/pdf/2607.11241v1","authors":"[\"Antoine Deza\",\"Yan Gerard\",\"Yijun Ma\",\"Sebastian Pokutta\"]","published":"2026-07-13T08:27:22Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.CO\"]","methods":"[]","has_code":false}