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
pdf copy (310kB) is available.