Counting polygon triangulations is hard
In some sense both of my accepted papers at SoCG are about a situation where I really wanted to prove something else, wasn’t able to, and wrote up what I could prove instead. The one whose preprint appears today, “Counting polygon triangulations is hard” (arXiv:1903.04737), proves that it’s \(\#\mathsf{P}\)-complete to count the triangulations of a polygon with holes.
It’s easy to prove that it’s \(\mathsf{NP}\)-hard to count maximum non-crossing subsets of line segment arrangements: the intersections graphs of line segments include all the planar graphs, so this follows immediately from the \(\mathsf{NP}\)-completeness of maximum independent sets in planar graphs. The gadgets in my paper (drawn below) turn a single line segment into a part of a polygon for which many triangulations use diagonals in approximately the same position as the line segment, and there are few other triangulations. By using these gadgets, one could easily construct a polygon in which most of the triangulations correspond to maximum non-crossing subsets, showing that it’s also \(\mathsf{NP}\)-hard to count triangulations. But this is unsatisfactory because it’s the wrong kind of completeness. For counting problems, we want \(\#\mathsf{P}\)-completeness, not just \(\mathsf{NP}\)-hardness.
The reason the outline above isn’t already a \(\#\mathsf{P}\)-completeness proof is that we need to control the rest of the triangulation better. It’s not enough for most triangulations to come from maximum non-crossing subsets. We need each maximum non-crossing subset of line segments to contribute exactly the same number of triangulations (or at least a predictable and controlled number) so that we can recover the number of maximum non-crossing subsets from the number of triangulations. The gadgets control the parts of the triangulation near each segment of the non-crossing subsets, but we also need to control the parts of the triangulation that are not near those segments. Achieving this took much of the work in my new paper. There are two main ideas: First, we use special arrangements with the property that, when you close off the gadgets of a maximum non-crossing subset, the remaining parts of the polygon form pieces of predictable shapes for which we can count the triangulations. In these arrangements, there are two colors of segments, red and blue; each blue segment is crossed by two red segments, and each red segment is crossed in the order blue-red-blue. So we need a new counting reduction from graph independent sets that produces arrangements of this type. And second, we decompose the total number of maximum non-crossing subsets into a sum of smaller numbers, of subsets that have a given number of red segments. Subsets with the same number of red segments leads to the same numbers of triangulations, allowing the terms in the sum to be recovered from the number of triangulations.
A secondary goal was to do this all using a polynomial-time counting reduction rather than the Turing reductions that are more commonly used for \(\#\mathsf{P}\)-completeness. One cannot use an even stronger notion of reduction, parsimonious reductions, to reduce \(\#\mathsf{P}\) problems that might have zero solutions to a problem like triangulation that always has at least one. But to me, counting reductions are more closely analogous to the many-one reductions used for \(\mathsf{NP}\)-completeness. We can use them, so we should use them. So the reductions in the paper are polynomial-time counting reductions, but more work would be needed to prove that the starting graph problem I used (counting independent sets in regular planar graphs) is complete for those reductions.
Surprisingly to me, this appears to be the first published proof of a \(\#\mathsf{P}\)-completeness result in two-dimensional computational geometry. And although some 2d geometric structures have been proven \(\mathsf{NP}\)-hard to construct (and therefore \(\mathsf{NP}\)-hard to count) it seems to be the first hardness proof of any kind for counting 2d structures that can be constructed rather than counted in polynomial time. But as I said at the top of this post, it’s not what I really wanted to prove. I was hoping to prove hardness for counting non-crossing structures on point sets, such as simple polygons, triangulations, non-crossing matchings, or pointed pseudotriangulations. The polygon question was suggested to me by Sara Billey when I visited her last April, in connection with a different problem we were working on (and still haven’t published). And counting the triangulations of a point set would fit the theme of my recent book, because this count is a numerical parameter that depends only on the order type of the points and mostly behaves monotonically under point deletion (exception: delete the center point of a quincunx). Instead I had to settle for polygon triangulations. But maybe another paper can take this line of research one step farther, to counting problems on points.