Table REF  displays versions of BNSL under sparsity constraints for the moralized graph. We now argue that there is little hope that one can efficiently find improvements of a given DAG by applying changes on its topological ordering. For all problem versions in Table REF  it is NP-hard to learn a DAG of a given score \(t\)  even when \(S_{\mathcal {F}}\)  is a DAG and \(t\)  is polynomial in \(n\)  and all local scores are integers [1]}, [2]}, [3]}. Observe that an acyclic superstructure has a topological ordering \(\tau \)  which is then automatically a topological ordering of every DAG where the parent sets are potential parent sets. Furthermore, observe that all the constraints on \(\mathcal {M}(D)\)  from Table REF  are true if \(D\)  does not contain arcs. Assume one can find improvements of a given DAG in polynomial time if the radius \(r\)  of the local search neighborhood is constant. Then, we can solve instances with acyclic superstructure by setting \(r=0\) , starting with an empty DAG and a topological ordering of \(S_\mathcal {F}\) , and improve the score \(t\)  times. This would be a polynomial time algorithm for instances where \(t\)  is polynomial in \(n\)  and \(S_\mathcal {F}\)  is a DAG which would imply \(\text{P}=\mathrm {NP} \) .
