6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Klaus Draeger Feb 22 '16 at 10:47
  • $\begingroup$ @KlausDraeger The point is input precision cannot exceed certain implicit requirements because of input length. I can make this explicit in problem. $\endgroup$ – user34945 Feb 22 '16 at 10:50
  • $\begingroup$ @KlausDraeger I made it $\Bbb Z$ which suffices for now. $\endgroup$ – user34945 Feb 22 '16 at 10:54
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – user34945 Feb 23 '16 at 11:09
  • $\begingroup$ Yes it is, there is a pretty straightforward reduction from subset sum. $\endgroup$ – Andreas Björklund Feb 23 '16 at 11:19
  • $\begingroup$ I do not see it could you please include? $\endgroup$ – user34945 Feb 23 '16 at 11:21
  • $\begingroup$ 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. $\endgroup$ – Andreas Björklund Feb 23 '16 at 11:33
  • $\begingroup$ @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$? $\endgroup$ – Brout Feb 24 '16 at 11:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy