The last post armed us with a powerful piece of polynomial-time computation, the FKT algorithm. In this post we’ll begin to explore how to leverage this to solve other problems under Valiant’s holographic framework by developing the basic theory of matchgrids, including the original proof of Valiant’s flagship Holant theorem, a first glimpse at a holographic reduction using these tools, and a reformulation (due to Cai/Choudhary) of everything in terms of tensors.
At a high level, just as FKT solves a counting problem, , related to a graph by tweaking until that counting problem becams something we know how to solve efficiently, namely the Pfaffian, the Holant theorem will allow us to solve counting problems related to by building out of a (planar) grid of “gadgets” called matchgates which capture the constraints related to the counting problem in question, so that the answer to the counting problem becomes something we know how to solve efficiently, namely . In particular, the counting problem is encoded by so that its answer is by construction equal to a particular function of the weighted edges of , an exponential sum of terms known as the Holant. We should think of the Holant as a global consolidation of all the local data needed to solve the counting problem at hand.
The whole point is that whereas we can rig the Holant to capture all this information because it’s defined as this huge exponential sum that we can’t hope to brute-force any more than we can our original problem, the FKT and Holant theorems imply that there are exponential cancellations among these terms, and solving the counting problem is as easy as computing the Holant is as easy as computing .
Of course, the tricky part is to define what the abovementioned “gadgets” are and how they can encode the local constraints we want. Before we introduce these key players, however, let’s play around with how we might encode the constraints of perfect matching locally.
1. Matchgates and Matchgrids
Our discussion at the beginning might come off as somewhat slow, but I’ll include it for those seeking motivation for all the definitions I’m throwing at the reader. For the time being, the following definitions will suffice.
Definition 1: A matchgate is the data of a weighted, undirected planar graph , a set of output nodes , and a set of input nodes . is said to be of arity .
We will restrict our attention to matchgates exclusively containing output nodes, called generators, and exclusively containing input nodes, called recognizers. All other matchgates are called transducers.
Definition 2: A matchgrid is the planar graph defined as the union of a set of generators , a set of recognizers , and a set of edges of weight 1, called wires, such that each input and output node in the matchgrid has exactly one incident wire.
Any perfect matching assigns to each of the wires a bit depending on whether that wire belongs in the matching. Consider the set of all possible bit vectors that can be assigned to the wires of . For a fixed , say that decomposes as the concatenation and for and denoting whether the input nodes in and respectively belong to wires assigned either 0 or 1.
Let be one of these wires, with output node belonging to generator and input node belonging to recognizer . If is assigned 0 (resp. 1) so that does not (resp. does) belong to the matching, the matching restricts to a perfect matching of a subgraph of including (resp. not including) and a perfect matching of including (resp. not including) .
The point is the following. For fixed , the contribution to of perfect matchings of coresponding to is where denotes the subset of output nodes of for which is an indicator bit vector, and is defined likewise.
More generally, for matchgate with output nodes and input nodes , define the standard signature of to be the matrix whose th entry is . Note that the standard signature of a generator (resp. recognizer) is a column (resp. row) vector. It follows that .
Our informal discussion is almost done; we just need a bit of formality to help transition into our actual treatment of matchgates. Let denote the standard basis . In the decomposition of for generator as a linear combination of all , the coefficient of is obviously . Define this as , and define the vector of all such values as . In other words, the signature of with respect to the standard basis is rigged to be the standard signature . The picture you should keep in mind is that generators emit from their output nodes all possible combinations of and particles, where each combination is weighted by the appropriate entry in .
What’s another fancy way to express the standard signature of a matchgate “dual” to the one we’ve just given (more on this in the last section)? The inner product of with for recognizer is also obviously . Define this as , and define as the vector of all such values; call this vector the signature of with respect to . Again, the signature of with respect to the standard basis is the standard signature . The picture here is that recognizers take in all combinations of and particles into their input nodes and spit out their values specified by the appropriate entries in .
2. Valiant’s Holant Theorem and Changes of Basis
Of course, this is pretty trivial given that we picked to be the standard basis. We could likewise have defined and for arbitrary bases consisting of vectors of length 2 (in fact we can also consider vectors of dimension for arbitrary , but that’s a topic for another post). Define the Holant of to be the quantity on the right-hand side of (1). The content of Valiant’s Holant Theorem is the following miracle:
Theorem 3: Identity (1) holds regardless of the choice of basis. In other words, .
Why should we care? Recall that our ultimate goal is to take our input graph , construct a matchgrid whose matchgates capture the local constraints of the counting problem at hand so that equals the solution to our counting problem, and compute the solution by efficiently computing . Different signatures encode different kinds of constraints, and the issue with the standard basis is that it can’t realize all signatures. The Holant theorem tells us this isn’t an issue because we can just use other bases.
Whether some basis can realize a particular signature for a given matchgate boils down to whether the corresponding system of polynomial equations is solvable. We will give a nice formulation of such a system in a future post, but for now let’s illustrate with an extended example.
Example 1: Let’s just consider matchgates with arity 2. What kinds of standard signatures exist? For starters, has an odd or even number of vertices, so if we take out an even or odd number of vertices respectively, we’re left with zero perfect matchings. In other words, must be a vector such that either 1) whenever is even, 2) whenever is odd. For arity 2, not only is this a necessary condition for a standard signature to be realizable, but it’s sufficient.
For all , and are realizable as standard signatures.
Proof: For the former signature, consider the path graph with three vertices whose endpoints are the output nodes and whose edge weights are and . For the latter signature, consider the path graph with four vertices, whose endpoints are the output nodes and whose edge weights are , , and 1.
Now what kinds of signatures are realizable by these matchgates in other bases? Consider the basis and a signature . For a generator with standard signature , the constraint that either or , combined with the definition of , implies that one of the following two polynomial systems must have a solution in :
So for example, for , the first equation is satisfied as long as the signature is of the form , while the second equation is satisfied as long as the signature is of the form .
3. A First Proof
The following is the original proof of Valiant’s Holant theorem. The idea is to blow the matchgrid up into an family of exponentially many matchgrids consisting of generators and recognizers of arity 1, each representing a possible combination of bits passed along the wires of , such that equals the contribution of to the Holant. We then build the matchgrid back up out of these components, arguing by linearity at each step that of each component equals its respective contribution to the Holant. At the end, we obtain a graph for which and agree, and we’re done.
Proof: Pick a fixed vector of particles assigned to the wires. We first claim that there exists a generator of arity 1 whose standard signature, if we allow “omittable nodes,” can be any 2-vector that we want. Consider the path graph on three vertices with edge weights and from left to right and output node the rightmost vertex. Normally, we’d say that the standard signature of this generator is . As a hackish fix, let’s also count matchings which potentially omit the leftmost vertex . Specifically, if we assign weight to vertex and weight to vertex , then as desired. For a given 2-vector , denote the corresponding arity-one generator by .
Say that emits some string of and particles from its output nodes. Then replace by the disjoint union of , and for each , rehook the wire originally going into the th output of into the output node of . We’ve purposely scaled up one of these arity-1 generators by so that these generators will emit with the same weighting as . Call this new matchgrid .
The point of all of this is that now,
(note that implicitly we’re weighting each recognizer vertex by 0).
To be explicit, any matching corresponds to a bitstring depending on whether the omittable nodes in our arity-1 generators are present, and in particular corresponds to an entry in , namely . If denotes so that , and denotes the input nodes of already occupied in our matching by a wire, the matchings corresponding to a particular such entry thus contribute to a total of . But by definition of as the inner product of with , is precisely .
The rest of the argument basically follows by linearity. Split into groups of elements each, where in each group all elements assign the same particles to the output nodes of . For any one group, say that the assignment to these output nodes is . For any , let , and define to be with the arity-1 generators corresponding to replaced once more by . We can now split the matchings of this new matchgrid up based on which particles outputs, concluding that .
Now we can keep playing this game; define to be for any , with the arity-1 generators corresponding to replaced once more by , so that . Continuing thus, we conclude that is precisely the Holant. But because we’ve gotten rid of all the omittable nodes we initially introduced.
Here’s our first example of a holographic algorithm. As a bit of background, recall the remark from the last post that while counting perfect matchings of planar graphs is easy, counting arbitrary matchings of planar graphs is -complete. In fact, a theorem by Vadhan says that counting matchings even in bipartite graphs of degree at most six is just as hard!
Let’s consider a slightly less ambitious problem. Say I wanted to compute the number of matchings in any bipartite graph where the left vertices have degree 2 and the right vertices have degree . Then I claim there exists a holographic algorithm solving this problem .
In fact, there exists a holographic algorithm for the so-called problem which subsumes the above as a special case: given a planar weighted bipartite graph whose left vertices have degree 2, compute the sum of the “masses” of all matchings. Here, the “mass” of a matching is the product of with . (For the previous problem, weight all the edges by 1 and note that ).
Given such a bipartite graph , we want to replace each left vertex by a generator of arity 2 which sends out at most 1 particle, i.e. ; this translates to the local constraint that a matching will contain at most one edge incident to any given left vertex. We want to replace each right vertex by a recognizer of arity which 1) outputs 0 when sent more than 2 particles, 2) outputs when sent exactly 1 particle along a wire of weight , 3) outputs when sent no particles. 1) captures the local constraint that a matching will contain at most one edge incident to any given right vertex. 2) captures the constraint of the first multiplicand defining “mass.” 3) captures the constraint of the second multiplicand.
By construction, the Holant will equal the product of the masses of all matchings: subsets of which aren’t matchings contribute nothing, while those that are matchings contribute precisely their mass to the Holant.
It remains to check that we can construct matchgates with the abovementioned signatures under some basis. For the generators, consider the single edge with output nodes both vertices and weight -1. Its standard signature is ( of the empty graph we will take to be 1), so we want 2-vectors and satisfying relevant polynomial constraints. I won’t bore you any further by writing these down, but suffice it to say that the basis with and works.
For the recognizers, consider the star graph on vertices and edge weights . Its standard signature is 0 at all entries corresponding to removing at most input nodes, and at the entry corresponding to removal of all but the input node corresponding to , and at the entry corresponding to removal of all nodes. The signature with respect to and is the one we want.
By Valiant’s Holant theorem and the FKT algorithm, we conclude that there exists a polynomial time algorithm for .
The key takeaway of this example is that the primary challenge of understanding the power of holographic algorithms is determining what collections of combinatorial constraints encoded by signatures are simultaneously realizable under a choice of bases for each wire? As you can tell from the above discussion about polynomial systems suggests, the question really boils down to determining whether the corresponding subvarieties of have nonempty intersection. More on this in a future post.
5. A Tensor Formulation
We now give an alternative formulation of the theory of matchgrids in terms of tensors, due to Cai/Choudhary. The motivation is that the statement of the Holant theorem and the fact that it holds trivially for the standard basis seems to suggest that if we stare closely at the definitions, there should probably be a nice, coordinate-free proof. Indeed, if we think about , , and the Holant in the right way, we can get a very quick proof of the Holant theorem.
The exposition will follow Cai/Choudhary’s 2005 paper “Valiant’s Holant Theorem and Matchgate Tensors.”
As above, let denote a basis of two column 2-vectors for and , and the standard basis, and regard the standard signature of a matchgate with outputs and inputs as a matrix so that is a column (resp. row) vector if is a generator (resp. recognizer). Also let be the transformation matrix defined b . We’ll assume is invertible for now.
If is a generator with inputs, then is the column vector defined by the equation . Writing as , we conclude that . On the other hand, if is a recognizer with inputs, then the original definition of tells us it’s merely .
In what sense are these two constructions dual to each other? Let denote the basis dual to such that ; define anlogously. Whereas is the vector of coefficients by which can be expressed in the basis , we can show that is the vector of coefficients by which can be expressed in the basis . Then implies that as desired.
Now consider a matchgrid with generators , recognizers , and wires . If and is its dual space, one observes that the Holant is merely the application of dual vector to . Alternatively, we could write the Holant as
The proof of the Holant Theorem is now quite straightforward: by our alternative definitions of and , we can write the two arguments of the inner product defining as and , from which we conclude that in any basis is equal to . Recall that this equals for combinatorial reasons, by our earlier discussion.
For the case where is not invertible, we just need that the span of contains for each generator , because then we can still define to be any one of the vectors for which . The Holant theorem follows in essentially the same way.
If denotes the tensor product of copies of and copies of , where , what the above discussion tells us is that should be thought of as living inside , inside should be thought of as living inside , and the Holant is merely the contraction of with . Specifically,
where and denote copies of the standard basis and dual basis indexed by the input/output nodes of the matchgate in question. Valiant’s Holant theorem then immediately follows merely for the abovementioned combinatorial reasons.
6. Two Unrelated Remarks
The first is that this is my first post using Prof. Luca Trevisan’s nifty LaTeX2WP script for converting TeX into something suitable for pasting into WordPress’s editor; highly recommended for anyone fed up with typing “” and hand-numbering section and theorem numbers in the tiny WP editor window!
The second is that my statement about Gaussian elimination as it relates to FKT from the previous post was incorrect. The polynomial-time algorithm we should be using is Berkowitz’ algorithm, because for numerical reasons we don’t want to use division.