Complexity of Inferences in Polytree-shaped Semi-Qualitative Probabilistic Networks

C. P. de Campos, F. G. Cozman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)


Semi-qualitative probabilistic networks (SQPNs) merge two important graphical model formalisms: Bayesian networks and qualitative probabilistic networks. They provide a very general modeling framework by allowing the combination of numeric and qualitative assessments over a discrete domain, and can be compactly encoded by exploiting the same factorization of joint probability distributions that are behind the Bayesian networks. This paper explores the computational complexity of semi-qualitative probabilistic networks, and takes the polytree-shaped networks as its main target. We show that the inference problem is coNP-Complete for binary polytrees with multiple observed nodes. We also show that inferences can be performed in linear time if there is a single observed node, which is a relevant practical case. Because our proof is constructive, we obtain an efficient linear time algorithm for SQPNs under such assumptions. To the best of our knowledge, this is the first exact polynomial-time algorithm for SQPNs. Together these results provide a clear picture of the inferential complexity in polytree-shaped SQPNs.
Original languageEnglish
Title of host publicationProceedings of the 27th AAAI Conference on Advances in Artificial Intelligence (AAAI)
PublisherAAAI Press
Number of pages7
Publication statusPublished - 2013

Bibliographical note

(acc.rate 29%, oral presentation, double-blind peer reviewed by >3 reviewers)


Dive into the research topics of 'Complexity of Inferences in Polytree-shaped Semi-Qualitative Probabilistic Networks'. Together they form a unique fingerprint.

Cite this