A Holant Dichotomy: Is the FKT Algorithm Universal?

Jin-Yi Cai, Zhiguo Fu, Heng Guo, Tyson Williams

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

We prove a complexity dichotomy for complex-weighted Holant problems with an arbitrary set of symmetric constraint functions on Boolean variables. This dichotomy is specifically to answer the question: Is the FKT algorithm under a holographic transformation [38] a universal strategy to obtain polynomial-time algorithms for problems over planar graphs that are intractable in general? This dichotomy is a culmination of previous ones, including those for Spin Systems [25], Holant [21, 6], and #CSP [20].
In the study of counting complexity, such as #CSP, there are problems which are #P-hard over general graphs but polynomial-time solvable over planar graphs. A recurring theme has been that a holographic reduction to FKT precisely captures these problems. Surprisingly, for planar Holant, we discover new planar tractable problems that are not expressible by a holographic reduction to FKT. In particular, a straightforward formulation of a dichotomy for planar Holant problems along the above recurring theme is false. In previous work, an important tool was a dichotomy for #CSPd, which denotes #CSP where every variable appears a multiple of d times. However the very first step in the #CSPd
dichotomy proof fundamentally violates planarity. In fact, due to our newly discovered tractable problems, the putative form of a planar #CSPd dichotomy is false when d ≥ 5. Nevertheless, we prove a dichotomy for planar #CSP2. In this case, the putative form of the dichotomy is true. We manage to prove the planar Holant dichotomy without relying on a planar #CSPd dichotomy for d ≥ 3, while the dichotomy for planar #CSP2 plays an essential role.
As a special case of our new planar tractable problems, counting perfect matchings (#PM) over k-uniform hypergraphs is polynomial-time computable when the incidence graph is planar and k ≥ 5. The same problem is #P-hard when k = 3 or k = 4, which is also a consequence of our dichotomy. When k = 2, it becomes #PM over planar graphs and is tractable again. More generally, over hypergraphs with specified hyperedge sizes and the same planarity assumption, #PM is polynomial-time computable if the greatest common divisor (gcd) of all hyperedge sizes is at least 5. It is worth noting that it is the gcd, and not a bound on hyperedge sizes, that is the criterion for tractability.
Original languageEnglish
Title of host publicationIEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages1259-1276
Number of pages18
DOIs
Publication statusPublished - 2015
EventFoundations of Computer Science 2015 - California, Berkley, United States
Duration: 17 Oct 201520 Oct 2015
http://ieee-focs.org/

Conference

ConferenceFoundations of Computer Science 2015
Country/TerritoryUnited States
CityBerkley
Period17/10/1520/10/15
Internet address

Fingerprint

Dive into the research topics of 'A Holant Dichotomy: Is the FKT Algorithm Universal?'. Together they form a unique fingerprint.

Cite this