Holographic Reduction: A Domain Changed Application and its Partial Converse Theorems

Date:2011-10-21

Holographic reductions between some Holant problems and some #CSP(Hd) problems are built, where Hd is some complex value binary function. By the complexity of these Holant problems, for each integer d >= 2, #CSP(Hd) is in P when each variable appears at most d times, while it is #P-hard when each variables appears at most d + 1 times. #CSP(Hd) counts weighted summation of graph homomorphisms from input graph G to graph Hd, and the maximum occurrence of variables is the maximum degree of G. We conjecture that the converse of holographic reduction holds for most of #Bi-restriction Constraint Satisfaction Problems, which can be regarded as a generalization of a known result about counting graph homomorphisms. It is shown that the converse of holographic reduction holds for some classes of problems.
-----------------------
Mingji Xia. Holographic Reduction: A Domain Changed Application and its Partial Converse Theorems. International Journal of Software and Informatics, 2011,5(4):567~577 http://www.ijsi.org/IJSI/ch/reader/view_abstract.aspx?file_no=i109&flag=1