W-BNSL generalizes the classical Bayesian Network Structure Learning (BNSL). In BNSL one is given a set \(N\)  of vertices and one local score \(s\)  for each pair consisting of a vertex \(v \in N\)  and a possible parent set \(P \subseteq N \setminus \lbrace v\rbrace \)  and the goal is to learn a DAG such that the sum of the local scores is maximal.
Thus, BNSL can be modeled with local multiscores \(\mathcal {F}(v)\)  containing triples \((P,s,0)\) .
Since BNSL is NP-hard [1]} and the weights \(\omega \)  are not used for this construction, W-BNSL is NP-hard even if \(k=0\) .
