Holographic Reduction: A Domain Changed Application and its Partial Converse Theorems
    Download PDF
Mingji Xia. Holographic Reduction: A Domain Changed Application and its Partial Converse Theorems. International Journal of Software and Informatics, 2011,5(4):567~577
Hits: 3159
Download times: 1907
Fund:This work is sponsored by the Chinese Academy of Sciences (CAS) start-up fund for CAS PresidentScholarship winner, the Hundred-Talent program of CAS under Angsheng Li, the Grand ChallengeProgram "Network Algorithms and Digital Information" of ISCAS, and NSFC 61003030.
Abstract: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.
keywords:holographic reduction  graph homomorphism  holant problem  #CSP  #BCSP
View Full Text  View/Add Comment  Download reader

 

 

more>>  
Visitor:2144304
Top Paper  |  FAQ  |  Guest Editors  |  Email Alert  |  Links  |  Copyright  |  Contact Us

© Copyright by Institute of Software, the Chinese Academy of Sciences
京ICP备05046678号-5

京公网安备 11040202500065号