Dichotomy theorems for holant problems
Jin‐Yi Cai, Michael Kowalczyk · 2010
We present dichotomy theorems within a class of problems known as holant problems. The holant framework deals with certain counting problems on graphs, and subsumes a wide variety of problems such as COUNTING WEIGHTED H-HOMOMORPHISMS, WEIGHTED #CSP, and also classical problems such as COUNTING VERTEX COVERS. In the absence of any direct knowledge about long-standing open questions such as “P = P#P?”, dichotomy theorems establish classes of problems for which every problem is in one of two complexity classes widely believed not to overlap. In the present work, we show that for a substantial subclass of holant problems, each problem is either in FP or #P-hard. Due to holographic algorithms, some of these #P-hard problems can be solved in polynomial time when the input is restricted to planar graphs, and we derive our dichotomy theorems under this restriction as well.