The Complexity of Finding kth Most Probable Explanations in Probabilistic Networks

DOI10.1007/978-3-642-18381-2_30zbMath1298.68202OpenAlexW1668352378WikidataQ59567629 ScholiaQ59567629MaRDI QIDQ3075529

Johan Kwisthout, Linda C. van der Gaag, Hans L. Bodlaender

Publication date: 15 February 2011

Published in: SOFSEM 2011: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-18381-2_30

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Most probable explanations in Bayesian networks: complexity and tractability ⋮ Most frugal explanations in Bayesian networks ⋮ Monomials in arithmetic circuits: complete problems in the counting hierarchy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of optimization problems
• Approximating MAPs for belief networks is NP-hard and other theorems
• Cost-based abduction and MAP explanation
• Finding MAPs for belief networks is NP-hard
• Simple characterizations of \(P(\# P)\) and complete problems
• Bayesian Networks and Decision Graphs
• On the complexity of unique solutions
• The Computational Complexity of Monotonicity in Probabilistic Networks