Parameterized Complexity of Probabilistic Inference in Ising Graphical Model
Ising图模型概率推理的参数化复杂性

Probabilistic inference of the Ising graphical model is to compute the partition function and the marginal probabilistic distribution through summing variables. Traditional computational complexity theory shows that the exact probabilistic inference of the Ising graphical model is#P-hard, and the approximate probabilistic inference is NP-hard.We analyzed the parameterized complexities of exact probabilistic inference of the Ising graphical model and the Ising mean field approximate inference. First, we proved the parameterized complexity theorems of probabilistic inference of the Ising graphical model with different parameters, which show that parameterized probabilistic inferences arc fixed parameter tractable with the variable number and the graphical model treewidth as parameters respectively. Then, we proved the parameterized complexity theorems of the Ising mean field, which demonstrate that the parameterized Ising mean field is fixed parameter tractable with the combination of the free distribution treewidth, the number of iteration steps and the number of variables as parameter; furthermore, when the Ising graphical model parameters satisfy the contraction condition of the Ising mean field iteration formula, the parameterized Ising mean field is fixed parameter tractable with the combination of the free distribution treewidth and the number of iteration steps as parameter.