Bounded-Support Additive Latin Transversals
via Color-Counted Matching
January 01, 1970
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<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=|\mathop{\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.
1 Introduction↩︎
In a January 2022 blog post, Eppstein highlighted the following open algorithmic question from a talk of Alon [1]. Fix a prime \(p\), a sequence \(A=(a_1,\dots,a_k)\in {(\mathbb{Z}_p)}^k\) with \(k<p\), and a \(k\)-subset \(B\subseteq \mathbb{Z}_p\). Can one order the elements of \(B\) as \(b_1,\dots,b_k\) so that the sums \(a_i+b_i\) are pairwise distinct? Alon proved that such an ordering always exists [2], but no polynomial-time construction is known. Consider the general case of an arbitrary cyclic group \(\mathbb{Z}_m\). Over \(\mathbb{R}\), pairwise distinct sums can be obtained by ordering the elements of \(A\) and \(B\) increasingly. The full-size case where \(k=m\) is governed by Hall’s theorem [3]1: For a sequence \(A=(a_1,\dots,a_m)\in(\mathbb{Z}_m)^m\), there is an ordering \(b_1,\dots,b_m\) of all elements of \(\mathbb{Z}_m\) such that the sums \(a_i+b_i\) are pairwise distinct if and only if \(\sum_{i=1}^m a_i\equiv 0 \pmod m\). Hall’s theorem extends to the case when \(A\) and \(B\) have size \(k=m-1\). Hence the cases \(k=m\) and \(k=m-1\) are completely characterized with the important remark that the solutions are constructible in polynomial time [3]. Apart from the brute-force polynomiality for fixed \(k\), the cases \(k=m\) and \(k=m-1\) are the only unrestricted regimes for which a polynomial-time construction is known. In this paper we study the algorithmic problem through the support size of the sequence \(A\). Let \(\mathop{\mathrm{supp}}(A)=\{c_0,\dots,c_{s-1}\}\) be the set of distinct values appearing in \(A\), and let \(s=|\mathop{\mathrm{supp}}(A)|\). Our main result is that bounded support makes the problem tractable: for arbitrary modulus \(m\), a solution can be found, whenever one exists, in randomized time \((k+\log m)^{O(s)}\). In particular, for every fixed support size \(s\), additive Latin transversals are constructible in randomized polynomial time. The central algorithmic tool behind the result is a generic colored matching primitive that we call Color-Counted Matching. In this problem, the input is an edge-colored graph together with prescribed target counts \(r_0,\dots,r_{h-1}\), and the task is to find a matching using exactly \(r_i\) edges of each color \(i\). We show in this paper that Color-Counted Matching can be solved by a randomized algorithm with running time \((|V|^2+|E|(q+1)^{h-1})^{O(1)}\), where \(q\) is the sum of the target counts and \(h\) is the number of colors. Thus, up to polynomial factors in the graph size, the dependence on the target matching size is \(q^{O(h)}\). This result uses the randomized exact matching algorithm of Mulmuley, Vazirani, and Vazirani [4]. The given parametric complexity of additive Latin transversals in \((k+\log m)^{O(s)}\) is an application of this more general result.
1.0.0.1 Organization.
Section 2 recalls the relevant existence results for additive Latin transversals and their connection with discrete tomography and matching integer programs. Section 3 states the main algorithmic results. Section 4 proves the reduction from Color-Counted Matching to Exact Red Matching and applies the theorem of Mulmuley, Vazirani, and Vazirani. Finally, we reduce additive Latin transversals to Color-Counted Matching and prove the bounded-support algorithm.
2 Related Results↩︎
We recall the main existence results for additive Latin transversals, explain their connection with discrete tomography, and discuss the relation of our contribution on Color-Counted Matching with the recent matching-ILP framework of Lassota and Ligthart [5].
Latin squares and their transversals have a long history in combinatorics. In the additive setting over a cyclic group, Hall’s theorem [3] gives a complete characterization in the full-size case. Namely, for a sequence \(A=(a_1,\dots,a_m)\in(\mathbb{Z}_m)^m\), there exists an ordering \(b_1,\dots,b_m\) of all elements of \(\mathbb{Z}_m\) such that the sums \(a_i+b_i\) are pairwise distinct if and only if \(\sum_{i=1}^m a_i \equiv 0 \pmod m\). Moreover, Hall’s theorem yields a polynomial-time construction. The near-full case \(k=m-1\) also follows from Hall’s theorem and is likewise polynomial-time constructible.
Alon [2] proved in 2000 that, for prime \(p\), every sequence \(a_1,\dots,a_k\in \mathbb{Z}_p\) with \(k<p\) and every \(k\)-subset \(B\subseteq \mathbb{Z}_p\) admits an ordering \(b_1,\dots,b_k\) such that the sums \(a_i+b_i\) are pairwise distinct. His proof uses the Combinatorial Nullstellensatz applied to the polynomial \[\prod_{1\le i<j\le k}(x_i-x_j)(a_i+x_i-a_j-x_j).\] Dasgupta, Károlyi, Serra, and Szegedy extended this existence phenomenon to \(\mathbb{Z}_{p^\alpha}\) and to \((\mathbb{Z}_p)^\alpha\) [6]. Gao and Wang later gave an alternative proof using group rings [7]. These results provide a strong existence theory, but they do not give a polynomial-time construction for the general repeated-sequence problem. Apart from the brute-force polynomiality when \(k=O(1)\) and the full or near-full cases \(k=m\) and \(k=m-1\), no general polynomial-time construction is known.
Alon’s and Hall’s additive-transversal theorems are naturally connected with discrete tomography. In discrete tomography one studies inverse problems in which a finite set of grid points, or equivalently a binary matrix, is reconstructed from prescribed line sums in several directions; these line sums are usually called X-rays [8]–[10].
From this viewpoint, Hall’s theorem on abelian groups [3], Del Lungo’s reconstruction theorem for sums of permutation matrices from diagonal sums [11], and Alon’s theorem can all be interpreted as periodic X-ray consistency results for permutation-type incidence structures. The chosen pairs form a periodic binary incidence matrix: one projection prescribes the selected elements of \(B\), another projection prescribes the multiset \(A\), and the all-different condition asks that the third projection be binary. This geometric viewpoint, which links our reconstruction problem to discrete tomography, is illustrated in Fig. 1.
This perspective explains why matching enters the picture. Thus the bounded-support additive-transversal problem may be viewed as a particularly structured instance of a broader discrete-tomography theme: reconstruction from three projections when one projection has bounded support.
On the algorithmic side, Color-Counted Matching is a primitive that appears naturally in the additive-transversal problem but is not specific to it. It includes Exact Matching as the two-color case, and it captures several exact-composition variants of matching problems. For instance, if all target counts are \(1\), it includes exact rainbow matching. It also gives a matching formulation of bounded-color versions of 3-dimensional matching: a triple \((x,y,z)\) may be represented as an edge \(xy\) colored by \(z\), and requiring prescribed counts for the \(z\)-colors enforces the corresponding constraints in the third coordinate. More generally, Color-Counted Matching captures colored perfect matchings arising in discrete tomography, tilings, permutation-matrix reconstruction, and cycle-cover problems. Some immediate consequences of our general theorem are stated after Theorem 2.
Our approach for solving Color-Counted Matching follows the same strategy as the recent matching-ILP framework of Lassota and Ligthart [5]. We use a reduction of Color-Counted Matching to the Exact Matching problem considered by Mulmuley, Vazirani, and Vazirani [4]: given a graph, a designated subset of red edges, and a target number of red edges, find a perfect matching with exactly that many red edges [4]. The theorem of Lassota and Ligthart applies to matching problems with additional linear constraints and therefore covers, as a black-box consequence, matching problems with prescribed color counts. This general result yields an XP dependence of order \(q^{O(h^2)}\). Our algorithm uses a more direct encoding of the relevant color-count constraints into one exact-weight constraint, followed by the exact-matching algorithm of Mulmuley–Vazirani–Vazirani. This simplifies the more general machinery of the matching-ILP framework and gives the sharper dependence \(q^{O(h)}\) for the additive-transversal instances. An analysis of Lassota–Ligthart’s algorithm for Color-Counted Matchings is available in the appendix.
3 Main Results↩︎
We now state the two algorithmic problems and the corresponding complexity bounds.
Definition 1. Fix a modulus \(m\). An Additive Transversal instance consists of an integer \(k\le m\), a multiset \(A=(a_1,\dots,a_k)\in(\mathbb{Z}_m)^k\), and a set \(B\subseteq \mathbb{Z}_m\) of cardinality \(k\). A solution is an ordering \(b_1,\dots,b_k\) of the elements of \(B\) such that the sums \(a_1+b_1,\dots,a_k+b_k\) are pairwise distinct in \(\mathbb{Z}_m\).
Let \(\alpha_0,\dots,\alpha_{s-1}\) be the distinct values appearing in \(A\), and let \(m_j\) be the multiplicity of \(\alpha _j\) in \(A\). Thus \(\sum_{j=0}^{s-1} m_j = k.\) Our main result is the parameterized complexity of a randomized algorithm whose running time is polynomial for each fixed support size \(s\), with an exponent depending linearly on \(s\).
Theorem 1. There is a randomized algorithm such that, on input an additive transversal instance over \(\mathbb{Z}_m\) with support size \(s=|\mathop{\mathrm{supp}}(A)|\), the algorithm either reports failure or outputs a correct solution. If a solution exists, then the algorithm outputs a solution with probability at least \(2/3\) in time \((k+\log m)^{O(s)}.\) The failure probability can be reduced by independent repetition. In particular, the problem is randomized polynomial-time solvable for every fixed support size \(s\).
The proof of Theorem 1 proceeds through a more general matching primitive, which we call Color-Counted Matching.
Definition 2. A Color-Counted Matching instance consists of a graph \((V,E)\), an edge coloring \(\chi:E\to \{0,\dots,h-1\}\), and nonnegative integer target counts \(r_0,\dots,r_{h-1}\). The task is to find a matching \(M\) such that \(|M\cap \chi^{-1}(i)|=r_i \qquad\text{for every }i\in \{0,\dots,h-1\}.\)
Let \(q=\sum_{i=0}^{h-1} r_i\). Every feasible solution of a Color-Counted Matching instance has exactly \(q\) edges. Thus, if \(|V|=2q\), every feasible solution is automatically a perfect matching. Similarly, in a bipartite graph \((L\sqcup R,E)\), if \(|L|=q\), then every feasible solution automatically saturates \(L\), while vertices of \(R\) may remain unmatched.
The following theorem shows that Color-Counted Matching is randomized polynomial-time solvable for every fixed number of colors.
Theorem 2. Let \((V,E)\) be a graph whose edges are colored with colors \(0,\dots,h-1\). Let \(r_0,\dots,r_{h-1}\) be prescribed target counts, and set \(q=\sum _{i=0}^{h-1} r_i\). There is a randomized algorithm which either reports failure or outputs a matching \(M\) such that \(|M\cap \chi^{-1}(i)|=r_i\) for every \(i\in\{0,\dots,h-1\}.\) If such a matching exists, then the algorithm outputs one with probability at least \(2/3\) in time \(\left(|V|^2+|E|(q+1)^{h-1}\right)^{O(1)}.\) The failure probability can be reduced by independent repetition. In particular, since any feasible matching has size \(q\), the problem is randomized polynomial-time solvable for every fixed number of colors \(h\). If the input graph is simple, then \(|E|\le |V|^2\) and \(q\le \frac{|V|}{2}\) on feasible instances, so the running time is bounded by \((|V|+|E|)^{O(h)}\).
Beyond additive transversals, Theorem 2 gives immediate fixed-color algorithms for several exact-composition matching problems.
First, it applies to the problem of tiling a region \(R\) of the triangular grid with prescribed numbers of lozenges in each orientation (the problem is illustrated in Fig. 2). Lozenge tilings of finite regions of the triangular lattice are equivalent to perfect matchings in the dual honeycomb graph. The three possible lozenge orientations induce a \(3\)-coloring of the edges. Every tiling corresponds to a perfect matching of the dual graph with three colors. Theorem 2 therefore gives a randomized algorithm with running time \(|R|^{O(1)}\), and hence polynomial time.
Figure 2: Reduction of the problem of tiling a region of the triangular grid with prescribed numbers of lozenges in each orientation to a Color-Counted Matching problem with three colors..
Second, directed cycle covers with prescribed arc-type counts reduce directly to Color-Counted Perfect Matching. Indeed, a directed cycle cover in a digraph \(D=(V,A)\) is equivalent to a perfect matching in the bipartite graph with left and right copies of \(V\), where an arc \(u\to v\) becomes the edge \(u_Lv_R\). If the arcs have \(h\) types, then the resulting Color-Counted Matching instance has \(2|V|\) vertices, \(|A|\) edges, and target matching size \(|V|\). Thus Theorem 2 gives a randomized algorithm with running time \((|V|^2+|A||V|^{h-1})^{O(1)}\).
Third, Theorem 2 applies to permutation matrices with prescribed diagonal sums. A permutation matrix of order \(N\) is a perfect matching in the bipartite graph between rows and columns. Coloring an edge \((i,j)\) by its diagonal class turns diagonal sums into color counts. If only \(h\) diagonal classes have nonzero prescribed sums, the other diagonals can be deleted, and the resulting bipartite graph has \(2N\) vertices, at most \(Nh\) edges, and target matching size \(N\). Theorem 2 therefore gives a randomized algorithm with running time \(N^{O(h)}\) for fixed \(h\).
The main application in this paper is to additive Latin transversals. Theorem 1 follows by reducing an additive transversal instance to the bipartite left-saturating version of Color-Counted Matching. In that reduction, the target matching size is \(q=k\), the number of colors is \(h=s\), and the diagonal graph has \(O(ks)\) vertices and \(ks\) edges. Therefore Theorem 2 gives a randomized running time \(k^{O(s)}\) in the unit-cost model, and the full bit complexity becomes \((k+\log m)^{O(s)}\).
4 Reductions and Algorithm↩︎
We now develop the reductions from additive Latin transversals to Color-Counted Matching, and from Color-Counted Matching to Exact Red Matching.
The key step is the reduction from a Color-Counted Matching instance with \(h\) colors to a two-color exact matching instance. The construction encodes the \(h\) prescribed color counts into a single red-edge target in a red-black augmented graph. This augmented graph is built so that feasible color-counted matchings in the original graph correspond exactly to perfect matchings with the prescribed number of red edges. This allows us to apply the randomized exact matching algorithm of Mulmuley, Vazirani, and Vazirani [4], and thereby solve Color-Counted Matching and additive Latin transversals.
4.1 From \(h\) colors to two colors↩︎
We first reduce Color-Counted Matching to Exact Red Matching.
Definition 3. An Exact Red Matching instance consists of a graph \((V,E)\), a set of red edges \(E_{\mathrm{red}}\subseteq E\), and an integer \(T\). The task is to find a perfect matching \(M\) such that \(|M\cap E_{\mathrm{red}}|=T\).
The Exact Red Matching problem is the special case of Color-Counted Matching with two colors, red and black, in which the matching is required to be perfect. Indeed, every perfect matching has \(\frac{|V|}{2}\) edges. Thus, prescribing the number of red edges of a perfect matching is equivalent to prescribing target counts \(r_{\mathrm{red}}\) and \(r_{\mathrm{black}}\) satisfying \(r_{\mathrm{red}}+r_{\mathrm{black}}=\frac{|V|}{2}\).
Figure 3: Reduction of a \(3\)-color Color-Counted Matching instance with targetcounts \((1,1,1)\) to an Exact Red Matching instance with \(21\) red edges.The Color-Counted Matching instance appears on the left, and the red-black\(Q\)-augmented graph appears on the right. The target matching size is\(q=1+1+1=3\), so \(Q=q+1=4\), and the red target is\(T=Q^0+Q^1+Q^2=1+4+16=21\). Corresponding solutions are shown below..
4.1.0.1 The red-black \(Q\)-augmented graph.
We now describe the construction of the Exact Red Matching instance. Let \(H=(V,E)\) be a Color-Counted Matching instance whose edges are colored with colors \(0,\dots,h-1\), and let \(r_0,\dots,r_{h-1}\) be the prescribed target counts. We denote \(q=\sum_{i=0}^{h-1} r_i\). Thus any matching satisfying the prescribed color counts has size \(q\).
If \(q>\lfloor \frac{|V|}{2}\rfloor\), then no matching of size \(q\) exists in an \(|V|\)-vertex graph, and we may immediately report failure. Hence we assume from now on that \(q\le \lfloor \frac{|V|}{2} \rfloor\). We set \(Q=q+1\).
The red-black \(Q\)-augmented graph \(H'=(V',E')\) is built from \(H\) as follows. The construction is illustrated in Fig. 3.
We initialize \(V'=V\) and \(E'=\emptyset\).
Each edge \(e=(u,v)\) of color \(i\) in \(E\) is replaced by a path \(u=x_{e,0},\;x_{e,1},\;\dots,\;x_{e,2Q^i-1}=v\) with \(2Q^i-1\) edges and \(2Q^i-2\) new internal vertices added to \(V'\) and used only for the edge \(e\).
The \(Q^i\) edges \(x_{e,2t}x_{e,2t+1}\) with \(0\le t<Q^i\) are colored red, while the \(Q^i-1\) edges \(x_{e,2t+1}x_{e,2t+2}\) with \(0\le t<Q^i-1\) are colored black. All these path edges are added to \(E'\).
If \(2q<|V|\), then we add to \(V'\) a set \(D\) of \(|V|-2q\) dummy vertices and join every vertex of \(D\) to every original vertex of \(V\) by a black edge. These dummy edges are added to \(E'\).
The target number of red edges in the Exact Red Matching instance is \(T=\sum_{i=0}^{h-1} r_iQ^i\).
4.1.0.2 Size of the red-black \(Q\)-augmented graph.
We now compute the size of the red-black \(Q\)-augmented graph. For an edge \(e\in E\) of color \(\chi(e)\), the replacement path has \(2Q^{\chi(e)}\) vertices and \(2Q^{\chi(e)}-1\) edges. Since the two endpoints of the path are the original endpoints of the edge, this replacement adds \(2Q^{\chi(e)}-2\) new vertices. Therefore \(|V'|=|V|+(|V|-2q)+\sum_{e\in E}(2Q^{\chi(e)}-2)\), and hence \(|V'|\le 2|V|+2|E|Q^{h-1}\).
Similarly, the path replacements contribute \(\sum_{e\in E}(2Q^{\chi(e)}-1)\) edges. The dummy vertices contribute \(|V|(|V|-2q)\) black edges, since each dummy vertex is joined to every original vertex. Hence \(|E'|=|V|(|V|-2q)+\sum_{e\in E}(2Q^{\chi(e)}-1)\), and therefore \(|E'|\le |V|^2+2|E|Q^{h-1}\).
Thus the red-black \(Q\)-augmented graph has size \(|H'|=O\!\left(|V|^2+|E|Q^{h-1}\right)\). Since \(Q=q+1\), this is \(|H'|=O\!\left(|V|^2+|E|(q+1)^{h-1}\right)\).
Remark 3. The construction of the red-black \(Q\)-augmented graph is not necessarily optimal. One could use mixed radices instead of the uniform base \(Q\). More precisely, if \(Q_i\) is a strict upper bound on the number of selected edges of color \(i\), one may define \(W_0=1\) and \(W_i=\prod_{j=0}^{i-1}Q_j\) for \(i\ge 1\), and replace the weight \(Q^i\) by \(W_i\). A preprocessing step could further reduce the size of the augmented graph by taking the target counts \(r_i\) into account. We do not use this optimization here.
4.1.0.3 Equivalence between \(h\) colors and two colors in the \(Q\)-augmented graph.
We now show the equivalence between the Color-Counted Matching instance in \(H\) and the Exact Red Matching instance in the red-black \(Q\)-augmented graph \(H'\).
Proposition 4. Let \(H=(V,E)\) be a Color-Counted Matching instance with colors \(0,\dots,h-1\) and target color counts \(r_0,\dots,r_{h-1}\). Let \(q=\sum_{i=0}^{h-1}r_i\), assume that \(q\le \lfloor \frac{|V|}{2}\rfloor\), and set \(Q=q+1\). Let \(H'=(V',E')\) be the red-black \(Q\)-augmented graph constructed above. Then \(H\) has a matching with the prescribed color counts if and only if \(H'\) has a perfect matching with exactly \(T=\sum_{i=0}^{h-1} r_iQ^i\) red edges.
Proof. We first prove that, given a solution \(M\) of the Color-Counted Matching instance, we can build a solution of the Exact Red Matching instance for the corresponding red-black \(Q\)-augmented graph with exactly \(T=\sum_{i=0}^{h-1} r_iQ^i\) red edges. Thus \(M\) contains exactly \(r_i\) edges of color \(i\) for every \(i\in\{0,\dots,h-1\}\), and therefore \(|M|=q\).
We build a matching \(M'\) in \(H'\) as follows. For each edge \(e=uv\) of \(M\), we select in \(M'\) all the red edges of the path replacing \(e\). For each edge \(e=uv\) of \(E\) that does not belong to \(M\), we select in \(M'\) all the black edges of the path replacing \(e\). Finally, we match the \(|V|-2q\) vertices of \(V\) that are not matched by \(M\) bijectively to the \(|V|-2q\) dummy vertices.
This gives a perfect matching of \(H'\). Indeed, in every path replacing an edge of \(H\), all internal vertices are matched. If the corresponding edge belongs to \(M\), then the two original endpoints are matched through the red edges of the path. If it does not belong to \(M\), then the black edges of the path match all internal vertices and leave the two original endpoints available. These available original vertices are either matched through another selected path or, if they are unmatched in \(M\), matched to dummy vertices.
The red edges selected in \(M'\) come only from the paths corresponding to the edges of \(M\). Each selected edge of color \(i\) contributes exactly \(Q^i\) red edges. Hence the total number of red edges in \(M'\) is \(\sum_{i=0}^{h-1} r_iQ^i=T\). Thus \(M'\) is a perfect matching of \(H'\) with exactly \(T\) red edges.
We now prove the converse implication. Assume that \(H'\) admits a perfect matching \(M'\) with exactly \(T\) red edges. We build from it a matching \(M\) in \(H\).
For each edge \(e=uv\) of \(H\), consider the alternating red-black path replacing \(e\) in \(H'\). Since the internal vertices of this path have no incident edges outside the path, a perfect matching of \(H'\) has only two possible states on this path: either it contains all the red edges of the path, or it contains all the black edges of the path. We call the path active in the first case and inactive in the second case. We select the edge \(e\) in \(M\) if and only if the path replacing \(e\) is active.
It follows that \(M\) is a matching in \(H\). Indeed, two active paths cannot share an original endpoint, since otherwise \(M'\) would contain two edges incident with the same vertex.
We now observe that \(M\) has exactly \(q\) edges. In the graph \(H'\), every dummy vertex is matched to an original vertex. Since there are \(|V|-2q\) dummy vertices, exactly \(|V|-2q\) original vertices are matched to dummy vertices. The remaining \(2q\) original vertices must be matched through active paths. Each active path uses exactly two original endpoints. Hence exactly \(q\) paths are active, and therefore \(|M|=q\).
For each \(i\in\{0,\dots,h-1\}\), let \(y_i\) be the number of selected edges of color \(i\) in \(M\). Equivalently, \(y_i\) is the number of active paths of weight \(Q^i\) in \(H'\). Since an active path of color \(i\) contributes exactly \(Q^i\) red edges, the number of red edges in \(M'\) is \(\sum_{i=0}^{h-1} y_iQ^i\). Since \(M'\) has exactly \(T\) red edges, \(\sum_{i=0}^{h-1} y_iQ^i=\sum_{i=0}^{h-1} r_iQ^i\).
We now use uniqueness of base-\(Q\) expansion. Since \(|M|=q\) and \(Q=q+1\), we have \(y_i<Q\) for every \(i\). Also, since \(r_i\le q\) and \(Q=q+1\), we have \(r_i<Q\) for every \(i\). Thus both sides of the previous equality are base-\(Q\) expansions with digits strictly smaller than \(Q\). Consequently, for every \(i\in\{0,\dots,h-1\}\), we have \(y_i=r_i\).
Therefore \(M\) contains exactly \(r_i\) edges of color \(i\), and so \(M\) is a solution of the original Color-Counted Matching instance. ◻
4.2 Proof of Theorem 2↩︎
The original result of Mulmuley–Vazirani–Vazirani places exact matching in randomized NC. In this paper we only use the resulting randomized polynomial-time search algorithm that we restate here.
Theorem 5 ([4]). Let \((V,E)\) be a graph, let \(E_{\mathrm{red}}\subseteq E\), and let \(T\ge 0\). There is a randomized algorithm running in time polynomial in \(|V|+|E|\) which either reports failure or outputs a perfect matching \(M\) such that \(|M\cap E_{\mathrm{red}}|=T.\) If such a perfect matching exists, then the algorithm outputs one with probability at least \(2/3\). If no such perfect matching exists, then the algorithm reports failure with probability \(1\). The success probability on yes-instances can be increased to \(1-\varepsilon\), for any \(\varepsilon>0\), by independent repetition, with an additional multiplicative factor \(O(\log(1/\varepsilon))\) in the running time.
The original theorem of Mulmuley–Vazirani–Vazirani applies to general graphs.
Applying Theorem 5 to the \(Q\)-augmented red-black graph \(H'\) gives a randomized algorithm whose running time is polynomial in \(|V'|+|E'|\). We now prove Theorem 2.
Proof of Theorem 2. Let \(q=\sum_{i=0}^{h-1}r_i\). If \(q>\lfloor \frac{|V|}{2}\rfloor\), then no matching of size \(q\) exists in \((V,E)\), and the algorithm reports failure. We therefore assume \(q\le \lfloor \frac{|V|}{2}\rfloor\), and set \(Q=q+1\).
We construct the red-black \(Q\)-augmented graph \(H'=(V',E')\) as in Proposition 4, and set the red target to be \(T=\sum_{i=0}^{h-1}r_iQ^i\). By Proposition 4, the original Color-Counted Matching instance has a solution if and only if \(H'\) has a perfect matching with exactly \(T\) red edges.
We now apply the exact matching theorem of Mulmuley–Vazirani–Vazirani to the red-black graph \(H'\) with red-edge set \(E'_{\mathrm{red}}\) and target \(T\), where \(E'_{\mathrm{red}}\) is the set of red edges of \(E'\). If such a perfect matching exists, the MVV algorithm outputs one with probability at least \(2/3\); if none exists, it reports failure with probability \(1\). Any returned perfect matching can be checked deterministically.
The running time for building the red-black \(Q\)-augmented graph is linear in its size, namely \(|V'|+|E'| = O\!\left(|V|^2+|E|Q^{h-1}\right)\). The MVV algorithm runs in time polynomial in the size of its input, so the total running time is \(\left(|V|^2+|E|Q^{h-1}\right)^{O(1)}.\) Since \(Q=q+1\), this is \(\left(|V|^2+|E|(q+1)^{h-1}\right)^{O(1)}\).
Finally, if the MVV algorithm returns a perfect matching of \(H'\) with exactly \(T\) red edges, the constructive correspondence in Proposition 4 allows us to extract the active path gadgets from it. These active gadgets form a matching of \(H\) with color-count vector \((r_0,\dots,r_{h-1})\). Hence the algorithm outputs a correct Color-Counted Matching solution. The failure probability can be reduced by independent repetition. ◻
4.3 From Additive Transversals to Color-Counted Matching↩︎
We now reduce the Additive Transversal problem to Color-Counted Matching. We consider an instance with 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\). Let \(\mathop{\mathrm{supp}}(A)=\{\alpha_0,\dots,\alpha_{s-1}\}\), and let \(m_j\) be the multiplicity of \(\alpha_j\) in \(A\).
We build a bipartite graph, called the diagonal graph of \(A\) and \(B\), as follows. The left vertex set is \(L=B\). The right vertex set is \(R=\{\alpha_j+b : 0\le j<s , \;b\in B\}\subseteq \mathbb{Z}_m\). For every \(b\in B\) and every \(j\in\{0,\dots,s-1\}\), we add the edge connecting \(b\) to \(b+\alpha_j\) and color it by \(j\). Thus the diagonal graph has \(k\) left vertices, at most \(ks\) right vertices, and exactly \(ks\) edges.
Lemma 1. The additive transversal instance with multiset \(A\) and set \(B\) has a solution if and only if the diagonal graph built from \(A\) and \(B\) has a matching saturating \(L\) and using exactly \(m_j\) edges of color \(j\) for every \(j\in \{0,\dots,s-1\}\).
Proof. We first assume that the additive transversal problem admits a solution. Thus the elements of the multiset \(A\) and the set \(B\) can be ordered as \(a_1,\dots,a_k\) and \(b_1,\dots,b_k\) so that the sums \(c_i=a_i+b_i\) are pairwise distinct.
For each index \(i\), let \(j(i)\) be the unique index such that \(a_i=\alpha_{j(i)}\). By construction of the diagonal graph, there is an edge from the left vertex \(b_i\) to the right vertex \(c_i=b_i+\alpha_{j(i)}\), and this edge has color \(j(i)\). Let \(M=\{\, b_i c_i : 1\le i\le k\,\}\). Since the vertices \(b_1,\dots,b_k\) are precisely the elements of \(B\), the matching \(M\) saturates \(L\). Moreover, since the sums \(c_1,\dots,c_k\) are pairwise distinct, no two edges of \(M\) have the same right endpoint. Hence \(M\) is indeed a matching.
It remains to check the color counts. For each color \(j\), the number of edges of color \(j\) in \(M\) is exactly the number of indices \(i\) such that \(a_i=\alpha_j\). This number is precisely the multiplicity \(m_j\) of \(\alpha_j\) in \(A\). Therefore \(M\) is a left-saturating matching using exactly \(m_j\) edges of color \(j\) for every \(j\in\{0,\dots,s-1\}\).
Conversely, assume that the diagonal graph admits a matching \(M\) saturating \(L\) and using exactly \(m_j\) edges of color \(j\) for every \(j\in\{0,\dots,s-1\}\). Since \(M\) saturates \(L=B\), each element \(b\in B\) is matched to a unique right vertex, say \(c_b\). If the edge \(bc_b\) has color \(j\), then by construction \(c_b=b+\alpha_j\). We assign the element \(a_b=\alpha_j\) to \(b\).
Because \(M\) uses exactly \(m_j\) edges of color \(j\), the assigned elements \(a_b\) contain each support value \(\alpha_j\) exactly \(m_j\) times. Hence the multiset \(\{a_b:b\in B\}\) is exactly \(A\). Finally, since \(M\) is a matching, the right endpoints \(c_b\) are pairwise distinct. Therefore the sums \(b+a_b=c_b\) are pairwise distinct.
Ordering the elements of \(B\) arbitrarily as \(b_1,\dots,b_k\) and taking the corresponding assigned elements \(a_{b_1},\dots,a_{b_k}\) gives an ordering of the multiset \(A\) such that the sums \(a_{b_i}+b_i\) are pairwise distinct. Thus the additive transversal instance has a solution. ◻
We now use Lemma 1 and the Color-Counted Matching algorithm to prove Theorem 1.
Proof of Theorem 1. We consider an additive transversal instance over \(\mathbb{Z}_m\), with \(|A|=|B|=k\), and we denote \(s=|\mathop{\mathrm{supp}}(A)|\). By Lemma 1, the instance reduces to a bipartite left-saturating Color-Counted Matching instance with matching size \(q=k\) and number of colors \(h=s\).
The diagonal graph has \(k\) left vertices, at most \(ks\) right vertices, and exactly \(ks\) edges. Since the desired matching saturates the left side, every feasible matching has size exactly \(k\). Thus the factor \((q+1)^{h-1}\) in Theorem 2 becomes \((k+1)^{s-1}\).
Let \(G_\Delta=(V_\Delta,E_\Delta)\) be the diagonal graph. Applying Theorem 2 gives a randomized algorithm with running time \(\left(|V_\Delta|^2+|E_\Delta|(k+1)^{s-1}\right)^{O(1)}\). Since \(|V_\Delta|=O(ks)\), \(|E_\Delta|=ks\), and \(s\le k\), this is bounded by \(k^{O(s)}\) in the unit-cost model.
It remains to account for the bit complexity of the arithmetic in \(\mathbb{Z}_m\). The construction of the diagonal graph requires computing residues \(b+\alpha_j \pmod m\), comparing them, and storing them. Each such operation uses numbers of \(O(\log m)\) bits and can therefore be performed in time polynomial in \(\log m\). Hence the total bit complexity is bounded by \[(k+\log m)^{O(s)}.\]
If the Color-Counted Matching algorithm returns a matching with the prescribed color-count vector, Lemma 1 converts it into a valid additive transversal. The returned solution can be checked deterministically. If a solution exists, the success probability is at least \(2/3\), and it can be amplified by independent repetition. This proves Theorem 1. ◻
Acknowledgments↩︎
Research reported in this paper was partially supported by the Berlin Mathematics Research Center MATH\(^+\) (EXC-2046/2, project ID 390685689), funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy as well as by the Natural Sciences and Engineering Research Council of Canada Discovery (Grant program number RGPIN-2026-06553).
5 Comparison with Lassota–Ligthart’s Theorem↩︎
The theorem of Lassota and Ligthart [5] applies to a broader class of matching problems with additional linear constraints. Color-Counted Matching is one special case of that framework. For this special case, the direct base-\(Q\) encoding bypasses some of the overhead of the general machinery and thus improves the dependence on the number of color-count constraints.
5.0.0.1 Color-Counted Matching as a matching-ILP.
Consider a Color-Counted Matching instance on a graph \(H=(V,E)\) with colors \(0,\dots,h-1\). Let \(r_0,\dots,r_{h-1}\) be the prescribed target counts. The matching formulation has one binary variable \(x_e\) for each edge \(e\in E\), together with the usual matching constraints \[\sum_{e\ni v} x_e \le 1 \qquad\text{for every } v\in V.\] The color-count constraints are \[\sum_{e:\chi(e)=i} x_e = r_i \qquad\text{for every } i\in\{0,\dots,h-1\}.\] Thus Color-Counted Matching is a matching-ILP with no additional variables and with \(h\) additional linear rows. The coefficients in these additional rows are in \(\{0,1\}\).
To avoid overloading notation, we write the parameters of Lassota–Ligthart’s theorem as follows: \(N\) for the number of edge variables, \(M\) for the size of the matching incidence block, \(a\) for the number of additional variables, and \(\ell\) for the number of additional rows. The theorem of Lassota and Ligthart yields a running time of the form \(\|c\|_\infty^{O(1)} N^{O(a+\ell)} \bigl(\Delta(M+\ell)\bigr)^{O((a+\ell)^2)}\).
For Color-Counted Matching, these parameters satisfy \(N=|E|\), \(a=0\), \(\ell=h\), \(\Delta=1\), and one may take \(M=O(|V|+|E|)\) up to the precise convention used for measuring the size of the matching incidence block. Thus, for Color-Counted Matching, we obtain the running time \[|E|^{O(h)}(|V|+|E|+h)^{O(h^2)}.\] In the fixed-size regimes relevant for this paper, where the matching size is \(q\) and the graph size is polynomial in \(q\) and \(h\), this becomes \(q^{O(h^2)}\). Thus, for Color-Counted Matching instances of bounded matching size, Lassota–Ligthart’s theorem yields a quadratic dependence on \(h\) in the exponent, namely \(q^{O(h^2)}\), whereas the direct reduction has a linear dependence, namely \(q^{O(h)}\).
5.0.0.2 Specialization to additive Latin transversals.
For the additive-transversal instances considered in this paper, the diagonal graph has \(k\) left vertices, at most \(ks\) right vertices, and exactly \(ks\) edges. The number of colors is \(h=s\), and the desired matching saturates the left side, so the target matching size is \(q=k\). Therefore we may take \(Q=k+1\). Applying Lassota–Ligthart’s theorem to the resulting Color-Counted Matching instance with \(N\le ks\), \(M=O(k+ks)\), \(a=0\), \(\ell=s\), and \(\Delta=1\) gives the bound \((ks)^{O(s)}(k+ks+s)^{O(s^2)} = k^{O(s^2)}\), up to factors depending only on \(s\) in the base. By contrast, the MVV exact matching algorithm via the direct reduction yields the running time \(k^{O(s)}\) in the unit-cost model, and \((k+\log m)^{O(s)}\) when arithmetic in \(\mathbb{Z}_m\) is counted in bit complexity.
5.0.0.3 Other fixed-composition matching applications.
The same comparison applies to other problems that are expressed as matchings with prescribed edge-type counts. For example, lozenge tilings of a finite region of the triangular lattice correspond to perfect matchings in the dual honeycomb graph. The three possible lozenge orientations induce three edge colors. Prescribing the number of lozenges in each direction is therefore a Color-Counted Perfect Matching problem with three colors. Since the matching is perfect, the total number of lozenges is fixed. Thus only two of the three orientation counts are independent. The Color-Counted Matching reduction gives a dependence in the exponent that is linear in the number of independent counting constraints, while Lassota–Ligthart’s theorem gives a quadratic dependence.
| Lassota–Ligthart’s theorem | Color-Counted Matching reduction | |
|---|---|---|
| Additional constraints | \(h\) additional linear rows | one scalar red-edge target |
| Encoding | general matching-ILP machinery | base-\(Q\) color-count encoding |
| Main overhead | proximity and mixed-ILP reductions | unary red-black path gadget |
| General CCM bound | \(|E|^{O(h)}(|V|+|E|+h)^{O(h^2)}\) | \(\left(|V|^2+|E|Q^{h-1}\right)^{O(1)}\) |
| Fixed-size regime | \(q^{O(h^2)}\) | \(q^{O(h)}\) |
| Additive-transversal | \(k^{O(s^2)}\) | \((k+\log m)^{O(s)}\) |
References↩︎
Hall’s theorem appears in the mathematics of juggling: in the language of periodic juggling patterns, it provides a necessary and sufficient condition for the feasibility of a prescribed throw sequence.↩︎