I'm studying the NP-Complete of Learning Bayesian Networks by the paper of David Maxwell Chickering, available in this link:
http://people.cs.pitt.edu/~milos/courses/cs3710/readings/chickering96learning.pdf
and i have the following question:
We see that the main objective of the proof is to show, by reducing an instance of DBFAS to 2-Learn, that Learning Bayesian Networks is also NP-Complete.
Each node in DBFAS instance became a variable in the 2-Learn Database, and each edge on DBFAS became 5 variables on 2-Learn. Here is where my questions begin:
Why 5 variables?
And so we have a prior network from DBFAS (see image). Why Hidden Nodes??
After that, Chickering writes the following:
"In the given instance of DBFAS, we know that each node in DBFAS is adjacent to either two or three nodes. For every node, wich is adjacent to exactly two other nodes in DBFAS, there is a hidden node in Bayesian Network and a edge from hi to xi. There are no other edges or hidden nodes in Bayesian Network..."
Why?
I would appreciate some help.
Image of some Adjacent node representation in Bayesian Network
