The current-best worst-case running time bound for exact algorithms for BNSL is \(2^n\cdot \text{\normalfont {poly}}(|I|)\)  where \(n\)  is the number of variables and \(|I|\)  is the size of the instance. Clearly, this running time is impractical for larger variable sets. Moreover, even very restricted special cases of BNSL remain NP-hard, for example the case where both every possible parent set has constant size and every variable has only a constant number of parent sets [1]}. Finally, restricting the topology of the DAG to sparse classes such as graphs of bounded treewidth or bounded degree leads to NP-hard learning problems as well [2]}, [3]}, [4]}.
