How to represent/implement the hypotheses class for a DAG learner
OK here is what I did: 

I read about the most specific $ms$ and most general $mg$ hypotheses here. Intuitively, the hypotheses class is defined as these two hypotheses and anything in between.  That is, for a hypothesis $h$ with DAG $G_h$, in order for $h$ to be in the hypotheses class $H$, it must be the case $G_{ms}\subseteq G_h \subseteq G_{mg}$. 

For now, I used only $ms$ since my problem transformed to learning only one labelling $\{+\}$.  Initially $G_{ms}=\emptyset$. Every example $x$ consist of pair of vertices $(x[a],x[b])$. if $\zeta(x)=\{+\}$ then there is an edge from $x[a]$ to $x[b]$ in $G_{ms}$ where $\zeta(x)$ is the labelling of $x$ according to the target function $h^*$. 

After seeing $i$ examples $G_{ms}$ has $i$ edges. Any hypothesis $h$ with $G_{ms}\subset G_h$ is included in my hypotheses class $H$.