NP-hardness of MAP in Ternary Tree Bayesian Networks

Cassio P. de CamposResearch 2013 · DOI

Abstract: This paper strengthens the NP-hardness result for the (partial) maximum a posteriori (MAP) problem in Bayesian networks with topology of trees (every variable has at most one parent) and variable cardinality at most three. MAP is the problem of querying the most probable state configuration of some (not necessarily all) of the network variables given evidence. It is demonstrated that the problem remains hard even in such simplistic networks.

Introduction: The MAP Inference Problem

In Bayesian Networks (BNs), Maximum A Posteriori (MAP) inference is the task of finding the most likely configuration of a subset of "query" variables given observed evidence. While calculating marginal probabilities in tree-structured networks is a classic example of an "island of tractability" (solvable in linear time), MAP inference is significantly more complex.

Previous research established that MAP is NP-hard for general networks. In tree structures, it was known to be NP-hard when variables have a cardinality of five ($z=5$). This technical report by Cassio P. de Campos pushes this boundary further, proving that the problem remains NP-hard even when variables are restricted to just three states (ternary variables).

Strengthening the Hardness Result

The core contribution is Theorem 3, which formally proves that the Decision-MAP problem is NP-hard for networks where the maximum cardinality of any variable is $z=3$ and the treewidth is $w=1$ (a tree). This result is significant because it shows that structural simplicity (a tree) combined with low variable cardinality (ternary) is still insufficient to guarantee efficient MAP inference.

The Reduction Gadget

To prove NP-hardness, the author employs a reduction from the Partition Problem: given a set of integers, can they be split into two subsets with equal sums? The author constructs a specific tree-structured Bayesian Network designed to encode the logic of this problem.

The Bayesian network structure used for the reduction, showing the chain of ternary variables $Y_i$ and the branching binary variables $X_i$ and $E_i$.

As shown in the figure above, the network consists of a chain of ternary variables ($Y_i$) that "carry" the cumulative state of the partition logic, binary variables ($X_i$) representing the choice of subset for each integer, and evidence variables ($E_i$ and $O$) that constrain the possible configurations.

Engineering Probabilities

The reduction relies on carefully engineered Conditional Probability Tables (CPTs). By setting probabilities based on the integers $t_i$ from the Partition Problem instance, the author ensures that the maximum probability of the network corresponds exactly to a valid solution of the Partition Problem.

The Conditional Probability Tables (CPTs) defining the relationships between variables in the reduction gadget.

The third state in the ternary $Y_i$ variables acts as a critical "buffer" or "accumulator." This state allows the network to track whether the partition logic has been violated, effectively encoding the sum-matching requirement into the probabilistic structure. The author also demonstrates that this reduction holds even with limited numerical precision (using rational numbers), ensuring its validity in standard computational models.

Conclusion and Future Work

By reducing the cardinality requirement from five to three, this work tightens the complexity bounds for MAP inference in Bayesian Networks. It highlights that "trees are easy" is a deceptive heuristic that only applies to specific types of queries.

One significant question remains: is MAP NP-hard in binary trees ($z=2$)? While this paper proves hardness for ternary variables, the complexity of the binary case remains an open problem, representing the final frontier in defining the tractability of MAP on trees.

Summary updated

Abstract

This paper strengthens the NP-hardness result for the (partial) maximum a posteriori (MAP) problem in Bayesian networks with topology of trees (every variable has at most one parent) and variable cardinality at most three. MAP is the problem of querying the most probable state configuration of some (not necessarily all) of the network variables given evidence. It is demonstrated that the problem remains hard even in such simplistic networks.
BibTeX
@inproceedings{campos2013np,
  author = {Cassio P. de Campos},
  title = {{NP-hardness of MAP in Ternary Tree Bayesian Networks}},
  booktitle = {Research},
  year = {2013},
  doi = {10.71910/supsi.6532},
}
Figure