T. Kocka, R. R. Bouckaert, M. Studeny: On the inclusion problem. Research report n. 2010, Institute of Information Theory and Automation, Prague, February 2001.

Every directed acyclic graph (DAG) over a finite non-empty set of variables (= nodes) N induces an independence model over N, which is a list of conditional independence statements over N. The inclusion problem is how to characterize (in graphical terms) whether all independence statements in the model induced by a DAG K are in the model induced by a second DAG L. Meek conjectured that this inclusion holds iff there exists a sequence of DAGs from K to L such that only arrow removal and 'legal' arrow reversal operations are performed to get the next DAG in the sequence.
In this report we give various characterizations of inclusion of DAG models and the proof of Meek's conjecture in the case that the DAGs K and L differ in at most one adjacency. As a warming up a rigorous proof of well-known graphical characterizations of equivalence of DAGs, which is a highly related problem, is given. Furthermore, we give intuition how to characterize inclusion of DAG models in general and describe possible strategies how to verify Meek's conjecture even if the DAGs K and L differ in more than one edge.

AMS classification 68T30

the inclusion problem
directed acyclic graph
Meek's conjecture
equivalence problem

A pdf copy (310kB) is available.