Special matchings: define a subset of arcs; are there perfect matchings with exactly k arcs from the subset? Not known whether in P or NP-complete.
In the symbolic matrix write x_ijz if (ij) is in the subset, x_ij otherwise. The symbolic determinant is a polynomial in z. If the coefficient a_k of z^k is not zero then there exist matchings with k arcs from the subset.
As before Pr {a_k = 0 | $matching}=1 /2. However a k cannot be computed directly. Fixed the x_ij values, take n +1 different values for z and interpolate the polynomial of degree n.