# 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>0$?

• I must be missing something. Given that you allow real values, can't any unbounded instance be trivially re-scaled to satisfy your bounds? This would make them irrelevant for the question. – Klaus Draeger Feb 22 '16 at 10:47
• @KlausDraeger The point is input precision cannot exceed certain implicit requirements because of input length. I can make this explicit in problem. – user34945 Feb 22 '16 at 10:50
• @KlausDraeger I made it $\Bbb Z$ which suffices for now. – user34945 Feb 22 '16 at 10:54

## 1 Answer

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 & I_n & 0\\I_n & I_n & 0\\0 & 0 & 1 \end{bmatrix}$$, where $$I_n$$ is a $$n\times n$$ identity matrix, and weights $$\begin{bmatrix}B & 0_n & 0\\0_n & 0_n & 0\\ 0& 0 & -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.

• Is problem $\mathsf{NP}$-complete if $|a_i|\approx2^m$? The problem seems still in $\mathsf{NP}$ right (input size is $m$ bits per edge for $\frac{m(m-1)}2$ edges)? – user34945 Feb 23 '16 at 11:09
• Yes it is, there is a pretty straightforward reduction from subset sum. – Andreas Björklund Feb 23 '16 at 11:19
• I do not see it could you please include? – user34945 Feb 23 '16 at 11:21
• Here is (almost) a written up reduction for what you want: Look at the Equal Weight Matching hardness reduction in dl.acm.org/citation.cfm?id=2722174. Then embed it as a zero weight matching problem. – Andreas Björklund Feb 23 '16 at 11:33
• @AndreasBjörklund what if only subset $I$ has $|I|=2\ll n$ which means bipartite graph has a perfect matching of size $n$ while subset sum has subset of size $2$ that sums to $t$? – T.... Feb 24 '16 at 11:52