Welcome to FAW2015, Guilin, Guangxi, China!

Is Valiant + FKT universal?

The Fisher-Kasteleyn-Temperley (FKT) algorithm can count the number of perfect matchings over planar graphs in polynomial time. For four decades this stood as the single most important counting problem that has a P-time algorithm over planar graphs while the same problem over general graphs is intractable.

In 2001, Les Valiant introduced matchgates, and holographic reductions to the FKT algorithm, known as holographic algorithms based on matchgates. They solve a number of counting problems over planar graphs, which are #P-hard over general graphs.

Over the past decade, a substantial theory has been developed, which aims to classify a broad class of counting problems by the local constraint functions that define them. Out of this work, a strong theme has emerged, which supports the following sweeping classification: All such locally defined counting problems can be classified into exactly 3 categories: (1) those that are P-time solvable over general graphs; (2) those that are P-time solvable over planar graphs but #P-hard over general graphs; and (3) those that remain #P-hard over planar graphs. Moreover, category (2) consists precisely of those problems that can be solved by Valiant's holographic reduction to the FKT. In other words, Valiant's holographic reduction followed by the FKT appears to be a universal strategy. This sweeping statement is supported by a number of complexity dichotomy theorems of ever broader scope, such as Spin Systems and Boolean #CSP.

In this talk, I will answer this question: Is Valiant + FKT universal?

Joint work with Zhiguo Fu, Heng Guo and Tyson Williams http://arxiv.org/abs/1505.02993