The pairwise counts for a pair of variables X i and X i not connected by an edge in G are

![0_image_0.png](0_image_0.png)

Condition (ii) is satisfied because the marginal counts for ea variable are identical. There are two types of pairwise count tables, thus, there are at most two values for a given type of pairwise LocalScore. By using the two pairwise count tables and Equations 1, 2, and 3, one can easily verify that the local scores for the two tables satisfy condition (iii). It follows from the symmetry in the two types of pairwise tables and condition (ii) that condition (iv)
is satisfied. It follows from the construction that condition (v) is satisfied. Furthermore, the set of cases is efficiently constructed and has a size which is polynomially bounded by the size of the graph G proving the result.

## 4. Conclusion

In this note, I show that the problem of finding the optimal path graphical models is NP- hard for a variety of common learning approaches. The negative result for learning optimal path graphical models stands in contrast to the positive result on learning tree graphical This hardness result highlights one potential source of the hardness. That is, models.

one can make an easy problem difficult by choosing an inappropriate subclass of models. Perhaps, by carefully choosing a broader class of models than tree graphical models one can identify interesting classes of graphical models for which the problem of finding an optimal model is tractable.

Another interesting class of graphical models not described in this note is the class of undirected graphical models (e.g., Lauritzen, 1996). The methods for learning undirected graphical models are closely related to the methods described in Section 2. In fact, for the case of undirected path models, the scoring formulas described in Section 2 are identical for each of the common approaches. Therefore, the NP-hardness result for directed path models presented in this note also applies to problem of learning undirected path models.

Finally, it is important to note that good heuristics exist for the problem of finding weighted Hamiltonian paths (Karp & Held, 1971). These heuristics can be used to identify good quality path models and rely on the fact that the optimal tree model can be easily found and will have a score at least as large as any path model.

## References

Boehnke, M., Lange, K., & Cox, D. (1991). Statistical methods for multipoint radiation hybrid mapping. American Journal of Human Genetics, 49, 1174–1188.

Chickering, D. (1996). Learning Bayesian networks is NP-complete. In Fisher, D., & Lenz, H. (Eds.), Learning from Data, pp. 121–130. Springer-Verlag.

Chow, C., & Liu, C. (1968). Approximating discrete probability distributions with dependence trees. IEEE Transactions on Information Theory, 14, 462–467.