Another dichotomy theorem

Jin-Yi Cai is one of the world’s experts on hardness of counting problems, especially those related to methods based on complex—pun intended—gadgets. He and his students have built a great theory of dichotomy, which we covered two years ago. This means giving conditions under which a counting problem in ${\mathsf{\#P}}$ must either be in ${\mathsf{P}}$ or be ${\mathsf{\#P}}$-complete, with no possibility in-between. The theory is built around a combinatorial algebraic quantity called the holant, which arose in Leslie Valiant’s theory of holographic algorithms.

Today Ken and I wish to discuss a recent paper on the hardness of counting the number of edge colorings, even for planar graphs.

This work is due to our dear friend Jin-Yi—who has been a colleague of each of us—with Heng Guo and Tyson Williams. It is entitled The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems. It is here. The extent to which algebra involving both rational and complex numbers is relevant is just one of several interesting things about the paper.

Their Main Result

They prove that counting the number of edge colorings of a planar graph is ${\mathsf{\#P}}$-hard. What is interesting is that it is easy, thanks to the four-color theorem, to show that every cubic biconnected planar graph is three-edge colorable. But counting how many such colorings is hard. Finding one is easy. Finding how many there are in total is hard.

This is a common situation in complexity theory. We have many examples of where finding one object is easy, but finding the total number is hard. This happens for example with perfect matchings, with satisfying assignments to ${\mathsf{2CNF}}$ formulas, and with many other situations.

Planar Graphs

One of my favorite type of graphs is planar graphs. You can draw them, picture them, visualize them. Even the Petersen graph and other important non-planar graphs graphs start to become, at least for me, harder to understand. It is no accident of nature that planar graphs have an efficient isomorphism algorithm, have good separators, and have many other special properties. Of course, thanks to the resolution of the Four-Color Conjecture, we know that any planar graph can be vertex-colored with at most four colors.

This makes Jin-Yi’s result more interesting, since planar graphs are special. His result, however, shows some surprising equivalences between counting problems for regular planar graphs and general graphs. This is one of the reasons that his machinery is interesting.

Complexity theory is often viewed as more difficult than other parts of theory. But I would argue that it is much the same as the area of algorithms, because complexity theory should be viewed as composed of algorithms. Often the algorithms are reductions that show that solving one problem is the same as solving another.

In Jin-Yi’s result he needs the existence of certain special gadgets. These gadgets allow him to prove the counting results. They handle signatures which are finite tuples of complex numbers under constraints. A key signature written ${\langle a,b,b\rangle}$ entails that the second and third numbers are equal and distinct from the first one. Others force all elements of a tuple to be equal, and so on. These conditions parameterize the statements of the counting problems, and the gadgets enable manipulating signatures so as to show reductions between these problems.

The gadgets are more intricate than in many other proofs, they require an understanding of certain number theory facts as well as other tricks. These together mean that the reductions are nontrivial and cause the resulting proof and paper to be long.

Bobby Fischer’s Role

The structure of their paper is great, so following the argument is not too difficult. But there are lots of details in their reductions, and so the best—as always—is to read the paper. Actually they supply a flowchart of their gadgets as follows:

They call the second bubble from the bottom the “Bobby Fischer gadget” because one choice of plan surprisingly achieves all of seven separate objectives. Fischer was indeed known for clarity as well as depth, so the comparison is apt.

What the gadget achieves is a way to simulate a richer set of “signatures” from certain base sets, so that a planar holant problem in the richer case polynomial-time Turing reduces to the planar holant problem for the original. Provided the base set includes ${\langle a,b,b \rangle}$ and ${\langle 1-\kappa, 1\rangle}$ where ${\kappa}$ is the size of a certain domain, “Bobby Fischer” shows that one can add the equality-of-four signature without increasing the complexity of the counting problem. Again we say to see the paper for the detailed lemma statement and proof.

A Taste Of Their Paper

We can, however, give here a taste of one of the key issues they face. Let’s take a look at what they call “the lattice condition.”

This is not a disease or malady of some kind. Rather it refers to a kind of independence of numbers. Let the numbers be

$\displaystyle \lambda_{1},\dots, \lambda_{m},$

all be non-zero complex numbers. Then they satisfy the lattice condition provided

$\displaystyle \lambda_{1}^{e_{1}} \cdot \lambda_{2}^{e_{2}} \cdots \lambda_{m}^{e_{m}} = 1,$

for integers ${e_{1},\dots,e_{m}}$ (not all zero), implies that ${e_{1} + \cdots + e_{m} \neq 0}$. For ease of insight, suppose the ${\lambda_i}$ are all positive real numbers. Then taking logarithms makes this mean that if ${e_{1}+\cdots + e_{m} = 0}$ for integers ${e_{1},\dots,e_{m}}$ not all zero, then

$\displaystyle e_{1}\log(\lambda_{1}) + \cdots + e_{m}\log(\lambda_{m}) \neq 0.$

If we remove the condition that the sum of the ${e's}$ are zero, then this would be exactly that the logs of the ${\lambda's}$ are linearly independent over the integers. The extra condition makes the lattice condition weaker. For example ${2,3,6}$ have the lattice condition, but their logarithms are not linearly independent:

$\displaystyle \begin{array}{rcl} 2^{x}3^{y}6^{z} &=& 1 \text{ implies } \\ 2^{x}2^{z}3^{y}3^{z} &=& 1. \end{array}$

This yields that ${x+z=0}$ and ${y+z=0}$. Thus assume that ${x+y+z=0}$. Then it follows that ${x+z + y+z = z = 0}$, which is a contradiction: all exponents must be nonzero.

Here is a sample lemma that they need:

Lemma 1 Let ${f}$ be a polynomial of degree ${n \ge 2}$ with rational coefficients. If the Galois group of ${f}$ over ${\mathbb{Q}}$ is ${S_{n}}$ or ${A_{n}}$ and the roots of ${f}$ do not all have the same complex norm, then the roots of ${f}$ satisfy the lattice condition.

Later they have an explicit infinite family of polynomials, and they want to show they all have the lattice condition, in the sense that their roots do. If they can show that they satisfy the above lemma they are done. Nothing is easy. So they must work hard to show via a clever argument that only a finite explicit subset of the infinite family of elements fail the lemma. These finitely many elements are shown to be handled by other arguments. The algebra for identifying these elements culminates in the formula

$\displaystyle \frac{1}{2097152(z+2)^6}\left(\begin{array}{cccccccc}&\!\!\!\!\!2097152z^{11} &\!\!\!\!\!+&\!\!\!\!\! 65277952z^{10} &\!\!\!\!\!+&\!\!\!\!\! 919728128z^9 &\!\!\!\!\!+&\!\!\!\!\! 7736969088z^8\\ +&\!\!\!\!\!43137332608z^7 &\!\!\!\!\!+&\!\!\!\!\! 167175471424z^6 &\!\!\!\!\!+&\!\!\!\!\! 458797435600z^5 &\!\!\!\!\!+&\!\!\!\!\! 889807335920z^4\\ +&\!\!\!\!\!1191781601633z^3 &\!\!\!\!\!+&\!\!\!\!\! 1045691960361z^2 &\!\!\!\!\!+&\!\!\!\!\! 537771428331^z &\!\!\!\!\!+&\!\!\!\!\! 121660965323\end{array}\right),$

which is needed only to be positive for ${z \geq 0}$.

Using Siegel’s Theorem

They do mention the famous theorem of Carl Siegel on integer solutions to equations of the form

$\displaystyle f(x,y) = 0.$

Siegel in 1929 proved that such an equation has only a finite number of solutions provided the polynomial ${f}$ satisfies a certain condition. Trivially we must avoid linear polynomials, since (e.g.)

$\displaystyle x+y = 0$

has an infinite number of solutions. An important special case of the finiteness theorem is
that

$\displaystyle ax^{3} + by^{3} = c,$

has only a finite number of solutions over the integers, provided ${a,b,c}$ are non-zero integers.

The theorem comes up in Jin-Yi’s paper because in constructing their proof they must show that a particular equation has only the “obvious” integer solutions. The Siegel theorem is helpful: it shows immediately that there are only a finite number of solutions. But the theorem gives no effective method that finds all the solutions. So they must show for this particular equation that all is okay. They succeed in doing this—and you may find this part of the paper quite interesting enough.

Open Problems

One obvious open problem is: could there be a short proof that counting colorings of planar graphs is ${\mathsf{\#P}}$-hard? Just because Jin-Yi’s proof is complex does not rule out the existence of a much simpler proof. I wonder…

[fixed definition of lattice condition]

1. June 24, 2014 2:39 am

Thanks for posting about this beautiful result. Recently you posted about proof-envy, and this morning I have the feeling that I want to use these theorems in some of my subsequent work 🙂

It is quite natural that decision problems in P have sharp-P-complete counting versions. Then there are again two cases: some of these sharp-P-complete problems are easy to approximate (they admit an FPRAS, a Fully Polynomial Randomized Approximation Scheme) and some of then cannot be FPRAS approximated unless RP = NP. Examples for the former are linear extensions of posets, perfect matchings in bipartite graphs, an example for the later is the number of cycles in directed graphs. So the next natural question is whether or not the number of edge-colorings of regular planar graphs can be well approximated. I know, the results what prof. Cai and his students achieved are already terrific, just I am curious 🙂

2. June 24, 2014 2:41 am

Reblogged this on countingcomplexity and commented:
Holants, Galois theorem, complexity dichotomy… Something extremely nice, and something we must learn.

June 26, 2014 11:57 am

Curious paper about P versus NP problem

http://hal.archives-ouvertes.fr/hal-00984866

Do you think is a serious proof?