On Zero sum perfect matching Fix $c\geq1$.

Input is a $m$ vertex complete graph with edges assigned $a_1,\dots,a_{\frac{m(m-1)}2}\in\Bbb Z$ in some order.

Is it $\mathsf{NP}$-complete to decide if there is a perfect matching of zero-sum for cases:

(A) $|a_i|\leq m^{\frac1c}$

(B) $|a_i|\leq\log^{c}m$?

I looked at the literature for perfect matching and subset sum and could not find this version. 

The closest was minimum weight perfect matching which has a polynomial time algorithm as in http://www.math.uwaterloo.ca/~bico/papers/match_ijoc.pdf which however in this case does not work.

It also seems like restricted version of subset sum and so the complexity is not obvious because of size of $|a_i|$.



Update: Including case C.

(C) What if $a_i$ needs roughly $m^\alpha$ bits for some fixed $\alpha&gt;0$?
The problem is in RP in both (A) and (B) by a variation of Lovasz's algorithm:
Fix a finite field $F$ of characteristic $2$ on at least $q=4m\max_i |a_i|$ elements.
Consider the graph's Tutte matrix $T(r)$ where you replace indeterminate $x_{ij}$ by $y_{ij}r^{a_{ij}+q/4}$, where $y_{ij}=y_{ji}$ is a uniformly and independently randomly chosen element in $F$ and $r$ is an indeterminate. Now observe that the determinant equals $\sum_{\mbox{Matching }M} \prod_{ij\in M} y_{ij}^2r^{2a_{ij}}$.
Hence, you can solve for the coefficient of $r^{q/2}$ in the polynomial $\operatorname{det} T(r)$ to see if there is a zero-sum matching. Compute the determinants of the numerical matrices $T_r$ obtained after replacing $r=1,2,\ldots, q$ in $T(r)$, and use interpolation to recover the coefficient. It is non-zero with probability at least $1-m/q$ if and only if the graph had a zero-sum matching.
Update: In (C) the problem is NP-complete.
Consider an instance $b_1,b_2,\ldots, b_n$ and $t$ to Subset Sum, i.e. is there a subset $I\subseteq [n]$ such that $\sum_{i\in I} b_i=t$?
We can embed this in a Zero-sum matching problem as follows. Consider the bipartite graph with biadjacency matrix $\begin{bmatrix}I_n &amp; I_n &amp; 0\\I_n &amp; I_n &amp; 0\\0 &amp; 0 &amp; 1 \end{bmatrix}$, where $I_n$ is a $n\times n$ identity matrix, and weights $\begin{bmatrix}B &amp; 0_n &amp; 0\\0_n &amp; 0_n &amp; 0\\ 0&amp; 0 &amp; -t \end{bmatrix}$
where $0_n$ is a $n\times n$ all-zero matrix and $B=\operatorname{diag}(b_1,b_2,\ldots,b_n)$ is a $n\times n$ diagonal matrix.
Now observe that there is a zero-sum perfect matching if and only if there is a solution to the Subset Sum instance.