# Learning Bayesian Networks Under Sparsity Constraints: A Parameterized
Complexity Analysis

Niels Grüttemeier111Contact Author and Christian Komusiewicz Fachbereich
Mathematik und Informatik, Philipps-Universität Marburg, Marburg, Germany
{niegru<EMAIL_ADDRESS>
###### Abstract

We study the problem of learning the structure of an optimal Bayesian network
$D$ when additional constraints are posed on the DAG $D$ or on its moralized
graph. More precisely, we consider the constraint that the moralized graph can
be transformed to a graph from a sparse graph class $\Pi$ by at most $k$
vertex deletions. We show that for $\Pi$ being the graphs with maximum degree
$1$, an optimal network can be computed in polynomial time when $k$ is
constant, extending previous work that gave an algorithm with such a running
time for $\Pi$ being the class of edgeless graphs [Korhonen & Parviainen, NIPS
2015]. We then show that further extensions or improvements are presumably
impossible. For example, we show that when $\Pi$ is the set of graphs with
maximum degree $2$ or when $\Pi$ is the set of graphs in which each component
has size at most three, then learning an optimal network is NP-hard even if
$k=0$. Finally, we show that learning an optimal network with at most $k$
edges in the moralized graph presumably has no
$f(k)\cdot|I|^{\mathcal{O}(1)}$-time algorithm and that, in contrast, an
optimal network with at most $k$ arcs in the DAG $D$ can be computed in
$2^{\mathcal{O}(k)}\cdot|I|^{\mathcal{O}(1)}$ time where $|I|$ is the total
input size.

##  1 Introduction

Bayesian networks are graphical models for probability distributions in which
the presence of conditional dependencies between a set of random variables are
represented via a directed acyclic graph (DAG) $D=(N,A)$ over a set $N$ of $n$
random variables Darwiche (2009). An arc from a vertex $u$ to a vertex $v$ in
a Bayesian network means that the distribution of $v$ depends on the value of
$u$. Once we have obtained a Bayesian network, one may infer the distribution
of some random variables given the values of other random variables.

First, however, one needs to learn the network from observed data. An
important step herein is to learn the _structure_ of the network, that is, the
arc set of the network. In this step, one is given for each network vertex $v$
and each set of possible parents of $v$ a parent score and the goal is to
learn an acyclic network with a maximal sum of parent scores. To represent the
observed data as closely as possible it may seem appropriate to learn a
tournament, that is, a DAG in which every pair of vertices $u$ and $v$ is
connected either by the arc $(u,v)$ or by the arc $(v,u)$. There are, however,
several reasons why learning a tournament-like DAG should be avoided (see
Darwiche (2009) for a detailed discussion): First, such a network gives no
information about which variables are conditionally independent. Second,
including too many dependencies in the model makes the model vulnerable to
overfitting. Finally, the problem of inferring distributions on a given
Bayesian network is intractable when the DAG is tournament-like. More
precisely, the inference problem on Bayesian networks is NP-hard Cooper
(1990). The key to obtaining efficient inference algorithms is to exploit that
the network is tree-like: If the moralized graph has small treewidth, the
inference task can be solved more efficiently Darwiche (2009); the moralized
graph of a network $D$ is the undirected graph on the same vertex set that is
obtained by adding an edge between each pair of vertices that is adjacent or
has a common child in $D$.

Motivated by these reasons for avoiding tournament-like networks and instead
aiming for tree-like networks, it has been proposed to learn optimal networks
under structural constraints that guarantee that the network or its moralized
graph is tree-like Elidan and Gould (2008); Korhonen and Parviainen (2013,
2015); Chow and Liu (1968); Gaspers et al. (2015). We continue this line of
research, focusing on exact algorithms with worst-case running time
guarantees. In other words, we want to find out for which structural
constraints there are fast algorithms for learning optimal Bayesian networks
under these constraints and for which constraints this is presumably
impossible.

#### Known Results.

The problem of learning a Bayesian network without structural constraints,
which we call Vanilla-BNSL, is NP-hard Chickering (1995) and can be solved in
$2^{n}n^{\mathcal{O}(1)}$ time by dynamic programming over all subsets of $N$
Ott and Miyano (2003); Silander and Myllymäki (2006).; later it was shown that
this running time can be achieved also within polynomial space Parviainen and
Koivisto (2009).

When the network is restricted to be a branching, that is, adirected tree in
which every vertex has indegree at most one, then an optimal network can be
computed in polynomial time Chow and Liu (1968); Gaspers et al. (2015). Note
that learning a more restricted Bayesian network is not necessarily easier:
While learning a branching is solvable in polynomial time, the problem becomes
NP-hard if we aim to learn a directed path Meek (2001).

On the negative side, the Bounded-tw-BNSL problem, where the moralized graph
of the network is restricted to have treewidth at most $\omega$ is NP-hard for
every fixed $\omega\geq 2$ and can be solved in
$3^{n}n^{\omega+\mathcal{O}(1)}$ time Korhonen and Parviainen (2013). Finally,
Bounded-vc-BNSL where the moralized graph is restricted to have a vertex cover
of size at most $k$ can be solved in $4^{k}\cdot n^{2k+\mathcal{O}(1)}$ time
Korhonen and Parviainen (2015); a vertex cover in a graph $G$ is a vertex set
$S$ such that every edge of $G$ has at least one endpoint in $S$. Since having
a bounded vertex cover implies that the graph has bounded treewidth, the
networks that are learned by Bounded-vc-BNSL allow for fast inference
algorithms. An algorithm with running time $f(k)\cdot|I|^{\mathcal{O}(1)}$ is
unlikely for Bounded-vc-BNSL, since Bounded-vc-BNSL is W[1]-hard with respect
to the parameter $k$ Korhonen and Parviainen (2015). Here, $|I|$ denotes the
total input size. In other words, it seems necessary that the degree of the
running time polynomial depends on $k$.

#### Our Results.

The results for Bounded-vc-BNSL Korhonen and Parviainen (2015) form the
starting point for our work. An alternative view of vertex covers is as
follows: A graph has a vertex cover of size $k$ if and only if it can be
transformed into an edgeless graph by $k$ vertex deletions. Thus, in Bounded-
vc-BNSL we learn a network whose moralized graph is close, in terms of the
number of vertex deletions, to a sparse graph class. We investigate whether
there are further positive examples for such constrained network learning
problems.

First, we consider the constraint that the moralized graph can be transformed
into a graph with maximum degree $1$ by at most $k$ vertex deletions. We show
that under this constraint, one can learn an optimal network in
$n^{\mathcal{O}(k^{2})}\cdot|I|^{\mathcal{O}(1)}$ time and thus in polynomial
time for every constant value of $k$. This extends the result for Bounded-vc-
BNSL in the following sense: the value of $k$ can be arbitrarily smaller than
the vertex cover number and thus for fixed $k$ our algorithm can learn an
optimal network for a larger class of graphs than the algorithm for Bounded-
vc-BNSL. Observe that the moralized graphs still have bounded treewidth and
thus inference on the learned networks will still be solvable efficiently.

We then show that it is unlikely that this positive result can be improved
much further. First, we show that an algorithm with running time
$f(k)\cdot|I|^{\mathcal{O}(1)}$ is unlikely. Moreover, we show that learning
an optimal network that has maximum degree $2$ is NP-hard and that learning an
optimal network in which every component has at most three vertices is NP-hard
(in a graph with maximum degree one every connected component has at most two
vertices).

We further extend these negative results by showing that even in the very
restricted scenario where we aim to compute an optimal network whose moralized
graph has at most $k$ edges, an $f(k)\cdot|I|^{\mathcal{O}(1)}$-time algorithm
is unlikely. In contrast, if we restrict instead the number of arcs in the
network, we obtain an algorithm with a running time of
$2^{\mathcal{O}(k)}\cdot|I|^{\mathcal{O}(1)}$. Thus, putting structural
constraints on the moralized graph may make the problem much harder than
putting similar structural constraints on the network itself. We obtain a
further hardness result for Vanilla-BNSL: Under standard assumptions in
complexity theory, it is impossible that we can transform a given instance of
Vanilla-BNSL in polynomial time to an equivalent one of size
$n^{\mathcal{O}(1)}$. Thus, it is sometimes necessary to keep an exponential
number of parent scores to compute an optimal network.

##  2 Preliminaries

###  2.1 Notation

We consider directed and undirected graphs that do not contain multiple edges.

A directed graph $D=(N,A)$ consists of a _vertex set_ $N$ and an _arc set_
$A\subseteq N\times N$. Let $D=(N,A)$ be a directed graph. If $D$ does not
contain directed cycles, then $D$ is called _directed acyclic graph_ (DAG). An
arc $(u,v)\in A$ is called _incoming arc into $v$_ and an arc $(v,u)\in A$ is
called  _outgoing arc from $v$_. The number of incoming arcs is called  _in-
degree of $v$_, and the number of outgoing arcs is the  _out-degree of $v$_. A
vertex without incoming arcs is a  _source_. A vertex without outgoing arcs is
a  _sink_. The set $P^{A}_{v}:=\\{u\in N\mid(u,v)\in A\\}$ is called _parent
set of $v$_. The vertices in $P^{A}_{v}$ are called _parents of $v$_ and for
every $u\in P^{A}_{v}$, the vertex $v$ is called _child of $u$_. We call
$v_{1}$ an _ancestor of $v_{\ell}$_ and $v_{\ell}$ a _descendant of $v_{1}$_
if there is a path $(v_{1},v_{2},\dots,v_{\ell})$ in $D$.

An undirected graph $G=(V,E)$ consists of a vertex set $V$ and an _edge set_
$E\subseteq\\{\\{u,v\\}\mid u,v\in V\\}$. For a vertex $v\in V$, we write
$N_{G}(v):=\\{u\mid\\{u,v\\}\in E\\}$ to denote the neighborhood of $v$ in
$G$. The _degree of a vertex $v$_ is defined as $\deg_{G}(v):=|N_{G}(v)|$. For
$V_{1},V_{2}\subseteq V$, we write
$E_{G}(V_{1},V_{2}):=\\{\\{v_{1},v_{2}\\}\in E\mid v_{1}\in V_{1},v_{2}\in
V_{2}\\}$ for the set of edges between $V_{1}$ and $V_{2}$. Moreover we set
$E_{G}(K):=E_{G}(K,K)$. Given an edge-set $E^{\prime}\subseteq E$, we let
$G\setminus E^{\prime}$ denote the graph we obtain after deleting the edges in
$E^{\prime}$ from $G$. Given a vertex-set $V^{\prime}\subseteq V$, we let
$G-V^{\prime}$ denote the graph we obtain after deleting the vertices in
$V^{\prime}$ and their incident edges from $G$. A set $T\subseteq E$ is called
_feedback edge set_ if $G\setminus T$ contains no cycles. The size of the
smallest possible feedback edge set for $G$ is called  _feedback edge number
of $G$_.A set $S\subseteq V$ is called _dissociation set_ , if $G-S$ has
maximum degree one. The size of the smallest possible dissociation set for $G$
is called  _dissociation number of $G$_.

A _graph class_ $\Pi$ is a set of undirected graphs. For a graph class $\Pi$
and $k\in\mathds{N}$, let $\Pi+kv:=\\{G=(V,E)\mid\exists V^{\prime}\subseteq
V:(|V^{\prime}|\leq k\land G-V^{\prime}\in\Pi)\\}$ denote the class of graphs
that can be transformed into a graph in $\Pi$ by performing at most $k$ vertex
deletions. Analogously, we define $\Pi+ke:=\\{G=(V,E)\mid\exists
E^{\prime}\subseteq E:(|E^{\prime}|\leq k\land G\setminus
E^{\prime}\in\Pi)\\}$ as the class of graphs that can be transformed into a
graph in $\Pi$ by performing at most $k$ edge deletions. We call $\Pi$
_monotone_ if $\Pi$ is closed under edge- and vertex deletions. Note that
$\Pi$ being monotone implies that for every $k\in\mathds{N}_{0}$, the graph
classes $\Pi+kv$ and $\Pi+ke$ are monotone.

###  2.2 Bayesian Network Structure Learning

#### Problem Definition.

Given a vertex set $N$, we call a family
$\mathcal{F}=\\{f_{v}:2^{N\setminus\\{v\\}}\to\mathds{N}_{0}\mid v\in N\\}$ ,
where every $f_{v}$ is a function that maps elements of
$2^{N\setminus\\{v\\}}$ to elements of $\mathds{N}_{0}$, a family of _local
scores_ for $N$. Intuitively, for a vertex $v\in N$ and some $P\in
2^{N\setminus\\{v\\}}$, the value $f_{v}(P)\in\mathds{N}_{0}$ represents the
score we obtain if we choose exactly the vertices of $P$ as parents for $v$.
Given a vertex set $N$, local scores $\mathcal{F}$, and some integer
$t\in\mathds{N}_{0}$, an arc set $A\subseteq N\times N$ is called
_$(N,\mathcal{F},t)$ -valid_ if $(N,A)$ is a DAG and $\sum_{v\in
N}f_{v}(P^{A}_{v})\geq t$.

Another important definition in context of Bayesian networks is the moralized
graph of a directed graph Elidan and Gould (2008). Given a directed graph
$D=(N,A)$, we call the undirected graph $\mathcal{M}(D):=(V,E_{1}\cup E_{2})$
with $V:=N$, $E_{1}=\\{\\{u,v\\}\mid(u,v)\in A\\}$, and
$E_{2}=\\{\\{u,v\\}\mid u\text{ and }v\text{ have a common child in }D\\}$ the
_moralized graph_ of $D$. The edges in $E_{2}$ are called  _moral edges_. We
may now define the problem.

$(\Pi+v)$-Bayesian Network Structure Learning ($(\Pi+v)$-BNSL)
Input: A set of vertices $N$, local scores $\mathcal{F}=\\{f_{v}\mid v\in
N\\}$, and two integers $t,k\in\mathds{N}_{0}$.

Question: Is there an $(N,\mathcal{F},t)$-valid arc set $A\subseteq N\times N$
such that $\mathcal{M}((N,A))\in\Pi+kv$?

Intuitively, $(\Pi+v)$-BNSL can be seen as a version of Vanilla-BNSL where we
add an additional constraint to the moralized graph of the resulting network.
Analogously to $(\Pi+v)$-BNSL, the problem $(\Pi+e)$-BNSL is defined on the
same input and we ask if there exists an $(N,\mathcal{F},t)$-valid arc set $A$
such that $(N,A)\in\Pi+ke$. For both problems we call the requested arc set
$A$ a _solution_ of the instance $(N,\mathcal{F},t,k)$. Note that, if $\Pi$ is
monotone, contains infinitely many graphs, and $k=n^{2}$, the property
$\mathcal{M}((N,A))\in\Pi+kv$ or $\mathcal{M}((N,A))\in\Pi+ke$ always hold,
since every edgeless graph and an empty graph belong to $\Pi$. Hence,
$(\Pi+v)$-BNSL and $(\Pi+e)$-BNSL are generalizations of Vanilla-BNSL and thus
NP-hard for every monotone and infinite $\Pi$. For formal reasons, the
problems are stated as decision problems. However, the algorithms presented in
this work solve the corresponding optimization problem within the same running
time.

#### Input representation.

Throughout this work, we let $n:=|N|$ denote the number of vertices given in
an instance $I=(N,\mathcal{F},t,k)$ of $(\Pi+v)$-BNSL or $(\Pi+e)$-BNSL.
Furthermore, we assume that the local scores $\mathcal{F}$ of an instance of
$(\Pi+v)$-BNSL or $(\Pi+e)$-BNSL are given in _non-zero representation_
Ordyniak and Szeider (2013), that is, for every $f_{v}\in\mathcal{F}$, each
value $f_{v}(P)$ is only given if it is different from zero. We assume that
for $N=\\{v_{1},\dots,v_{n}\\}$, the local scores $\mathcal{F}$ are given as a
two-dimensional array $\mathcal{F}:=[Q_{1},Q_{2},\dots,Q_{n}]$, where each
$Q_{i}$ is an array containing all triples $(f_{v_{i}}(P),|P|,P)$ where
$f_{v_{i}}(P)>0$. The size $|\mathcal{F}|$ is then defined as the number of
bits we need to store this two-dimensional array. As the _size of $I$_ we
define $|I|:=n+|\mathcal{F}|+\log(t)+\log(k)$.

#### Potential Parents.

In this work, we consider $(\Pi+v)$-BNSL and $(\Pi+e)$-BNSL for some monotone
graph classes $\Pi$. Observe that in these cases the following holds.

###### Proposition 1

Let $\Pi$ be a monotone graph property, and let $(N,\mathcal{F},t,k)$ be a
yes-instance of $(\Pi+v)$-BNSL (or $(\Pi+e)$-BNSL). Then, there exists a
solution $A$ for $(N,\mathcal{F},t,k)$ such that for every $v\in N$ it holds
that $f_{v}(P_{v}^{A})=0$ implies $P_{v}^{A}=\emptyset$.

###### Proof

Let $A$ be a solution for $(N,\mathcal{F},t,k)$ such that there exist vertices
$v_{1},\dots,v_{\ell}\in N$ with $P_{v_{i}}^{A}\neq\emptyset$ and
$f_{v_{i}}(P_{v_{i}}^{A})=0$. We then set
$A^{\prime}:=A\setminus\\{(u,v_{i})\mid u\in N,i\in\\{1,\dots,\ell\\}\\}$.
Observe that $P_{v_{i}}^{A^{\prime}}=\emptyset$ for all
$i\in\\{1,\dots,\ell\\}$. Moreover, it trivially holds that
$f_{v_{i}}(P^{A^{\prime}}_{v_{i}})\geq f_{v_{i}}(P^{A}_{v_{i}})$ and
$(N,A^{\prime})$ is a DAG. Therefore, $A^{\prime}$ is
$(N,\mathcal{F},t)$-valid. Finally, since $\mathcal{M}((N,A))\in\Pi+kv$ and
$\Pi$ is monotone, we conclude $\mathcal{M}((N,A^{\prime}))\in\Pi+kv$.
Obviously, the same holds for $\Pi+ke$. Therefore, $A^{\prime}$ is a solution
of $(N,\mathcal{F},t,k)$ such that for every $v\in N$ it holds that
$f_{v}(P_{v}^{A^{\prime}})=0$ implies $P_{v}^{A^{\prime}}=\emptyset$.
$\hfill\Box$ ■

Given an instance $I:=(N,\mathcal{F},t,k)$ and some $v\in N$, we define the
_set of potential parents of $v$_ by
$\mathcal{P}_{\mathcal{F}}(v):=\\{P\subseteq
N\setminus\\{v\\}:f_{v}(P)>0\\}\cup\\{\emptyset\\}$, which are exactly the
parent sets stored in $\mathcal{F}$ together with the empty set. If $\Pi$ is
monotone, we can assume by Proposition 1 that in a solution $A$ for $I$, every
$v$ has a parent set $P^{A}_{v}\in\mathcal{P}_{\mathcal{F}}(v)$. An important
measurement for the running times of our algorithms is the maximum number of
potential parent sets $\delta_{\mathcal{F}}$ which is is formally defined by
$\delta_{\mathcal{F}}:=\max_{v\in N}|\mathcal{P}_{\mathcal{F}}(v)|$ Ordyniak
and Szeider (2013). Given a vertex $v\in N$, we can iterate over all vertices
in potential parent sets of $v$ in $\mathcal{O}(\delta_{\mathcal{F}}\cdot n)$
time.

Another tool for designing algorithms for BNSL problems is the superstructure
Ordyniak and Szeider (2013). Let $N$ be a vertex set with local scores
$\mathcal{F}$. The _superstructure_ of $N$ and $\mathcal{F}$ is the directed
graph $S_{\vec{\mathcal{F}}}=(N,A_{\mathcal{F}})$ with
$A_{\mathcal{F}}=\\{(u,v)\mid\exists P\in\mathcal{P}_{\mathcal{F}}(v):u\in
P\\}$. That is, there exists an arc $(u,v)\in A_{\mathcal{F}}$ if and only if
$u$ is a potential parent of $v$. Obviously, given $N$ and $\mathcal{F}$, the
superstructure $S_{\vec{\mathcal{F}}}$ can be constructed in polynomial time
in $n$ and $|\mathcal{F}|$. Throughout this work we let $m:=|A_{\mathcal{F}}|$
denote the number of arcs in the superstructure. Note that $m<n^{2}$.

###  2.3 Parameterized Complexity

A problem is called _slicewise polynomial (XP)_ for a parameter $k$ if it can
be solved in time $\mathcal{O}(|I|^{f(k)})$ for a computable function $f$.
That is, the problem is solvable in polynomial time when $k$ is constant. A
problem is called  _fixed-parameter tractable (FPT)_ for a parameter $k$ if it
can be solved in time $f(k)\cdot|I|^{\mathcal{O}(1)}$ for a computable
function $f$. If a problem is W[1]-hard then it is assumed to be fixed-
parameter _intractable_. A problem has a polynomial kernel for a parameter $k$
if there is a polynomial-time algorithm that, given an instance $I$ with
parameter $k$, computes an equivalent instance $I^{\prime}$ with parameter
$k^{\prime}\leq k$ of size $g(k)$ where $g$ is a polynomial. For a detailed
introduction into parameterized complexity we refer to Cygan et al. (2015).

##  3 Vertex Deletion Distances

###  3.1 BNSL with Bounded Dissociation Number

Let $\Pi_{1}:=\\{G\mid G\text{ has maximum degree }1\\}$, that is, every
$G\in\Pi_{1}$ consists only of isolated edges and isolated vertices. Observe
that $\Pi_{1}$ is monotone. In this section we consider $(\Pi_{1}+v)$-BNSL.
Note that, given some $k\in\mathds{N}$, a DAG $D=(N,A)$ with
$\mathcal{M}(D)\in\Pi_{1}+kv$ is a DAG whose moralized graph has a
dissociation set of size at most $k$. Since the treewidth of a graph is never
bigger than the dissociation number plus one, the moralized graph of the
resulting Bayesian network has treewidth at most $k+1$. Before we describe the
main idea of the algorithm we provide the following simple observation about
Bayesian networks whose moralized graph has a bounded dissociation number.

###### Proposition 2

Let $D=(N,A)$ be a DAG and $S\subseteq N$ be a dissociation set of
$\mathcal{M}(D)$. Then, at most $2|S|$ vertices in $N\setminus S$ have
descendants in $S$.

###### Proof

Let $v\in S$. We say that a vertex $w\in N\setminus S$ is an  _external
ancestor of $v$_ if there exists a path $(w,w_{1},\dots,w_{\ell},v)$ in $D$
such that $w_{i}\in N\setminus S$ for all $i\in\\{1,\dots,\ell\\}$. We prove
the proposition by showing that every vertex in $S$ has at most two external
ancestors.

First, assume $v$ has three distinct parents $w_{1},w_{2},w_{3}$ outside $S$.
Then, there are moral edges $\\{w_{1},w_{2}\\},\\{w_{2},w_{3}\\}$, and
$\\{w_{3},w_{1}\\}$ forming a triangle outside $S$ in $\mathcal{M}(D)$. This
contradicts the fact that $S$ is a dissociation set of $\mathcal{M}(D)$.
Hence, every $v\in S$ has at most two parents outside $S$. Next, consider the
following cases.

Case 1: $|P^{A}_{v}\setminus S|=0$. Then, $v$ has no external ancestors and
nothing more needs to be shown.

Case 2: $|P^{A}_{v}\setminus S|=1$. Then, let $P^{A}_{v}\setminus S=\\{w\\}$.
Since $S$ is a dissociation set of $\mathcal{M}(D)$ it holds that
$\deg_{\mathcal{M}(D)-S}(w)\leq 1$. Hence, $w$ has at most one parent
$w^{\prime}$ outside $S$. Moreover, since
$\deg_{\mathcal{M}(D)-S}(w^{\prime})\leq 1$, the vertex $w^{\prime}$ has no
parent in $N\setminus S$. Therefore, $v$ has at most two external ancestors.

Case 3: $|P^{A}_{v}\setminus S|=2$. Then, let $P^{A}_{v}\setminus
S=\\{w_{1},w_{2}\\}$. Note that $\\{w_{1},w_{2}\\}$ is a moral edge in
$\mathcal{M}(D)$. Then, since $\deg_{\mathcal{M}(D)-S}(w_{1})\leq 1$ and
$\deg_{\mathcal{M}(D)-S}(w_{2})\leq 1$, the vertices $w_{1}$ and $w_{2}$ do
not have parents in $N\setminus S$. Therefore, $v$ has exactly two external
ancestors. $\hfill\Box$ ■

The idea is the following: If we know the dissociation set $S$, all their
ancestors $Q$ under $A$, and the arcs between them, the remaining arcs of $A$
can be found in polynomial time. We start with the following definition .

###### Definition 3

let $N$ be a vertex set and let $S\subseteq N$. A set $Q\subseteq N\setminus
S$ together with an arc-set $A_{Q}\subseteq(S\cup Q)\times(S\cup Q)$ is called
_ancestor tuple for $S$_, if

  1. a)

$D_{Q}:=(S\cup Q,A_{Q})$ is a DAG, and

  2. b)

for every $v\in Q$ exists some $w\in S$ such that $w$ is a descendant of $v$
in $D_{Q}$, and

  3. c)

in the moralized graph $\mathcal{M}(D_{Q})$, every $v\in Q$ has at most one
neighbor outside $S$.

Intuitively, the ancestor tuple $\langle Q,A_{Q}\rangle$ is the part of the
solution that our algorithm finds via bruteforce. We next formally define an
arc set containing the remaining arcs of a solution. To this end, we introduce
some notation. Given an ancestor tuple $\langle Q,A_{Q}\rangle$ of some
$S\subseteq N$, we let $R:=N\setminus(S\cup Q)$ denote the remaining vertices
of $N$. Moreover, we define $Q_{0}:=\\{v\in
Q\mid\deg_{\mathcal{M}(D_{Q})-S}(v)=0\\}$ and $Q_{1}:=Q\setminus Q_{0}$. By
Definition 3 $c)$, the vertices of $Q_{1}$ are the vertices that have degree
one in $\mathcal{M}(D_{Q})-S$.

###### Definition 4

Let $N$ be a vertex set, let $S\subseteq N$, and let $\langle Q,A_{Q}\rangle$
be an ancestor tuple of $S$. An arc-set $A_{R}\subseteq(S\cup Q_{0}\cup
R)\times R$ is called _suitable for $\langle Q,A_{Q}\rangle$_ if $A_{R}$
contains no self-loops, and every $w\in Q_{0}\cup R$ has at most one incident
arc in $A_{R}\cap((R\cup Q_{0})\times R)$.

Next, we state the connection between Definitions 3, 4, and DAGs whose
moralized graph has dissociation set $S$. First, an ancestor tuple for some
$S$ and a suitable arc set can be combined to a DAG where $S$ is a
dissociation set of the moralized graph.

###### Proposition 5

Let $N$ be a vertex set, let $S\subseteq N$, let $\langle Q,A_{Q}\rangle$ be
an ancestor tuple of $S$, and let $A_{R}\subseteq(S\cup Q_{0}\cup R)\times R$
be a suitable arc set for $\langle Q,A_{Q}\rangle$. It then holds that

  1. 1.

$D:=(N,A_{Q}\cup A_{R})$ is a DAG, and

  2. 2.

$S$ is a dissociation set of $\mathcal{M}(D)$.

###### Proof

We first show that $D$ is a DAG. Assume towards a contradiction that there is
a directed cycle in $D$. Since $\langle Q,A_{Q}\rangle$ is an ancestor tuple
we conclude from Definition 3 $a)$ that there is no directed cycle in
$(N,A_{Q})$. Hence, there is an edge $(v,w)\in A_{R}$ that is part of the
cycle. Note that $w\in R$ and there exists an outgoing edge $(w,w^{\prime})\in
A_{Q}\cup A_{R}$ that is also part of the cycle. Since no edge in $A_{Q}$ is
incident with vertices of $R$ we conclude $(w,w^{\prime})\in A_{R}$ and
therefore $w^{\prime}\in R$. Note that $w^{\prime}\neq w$, since $A_{R}$
contains no self-loops. Since $(w,w^{\prime})$ is part of the directed cycle,
there exists an edge $(w^{\prime},w^{\prime\prime})\in A_{R}$ with
$w^{\prime\prime}\in R$. Then, $w^{\prime}$ is incident with two arcs in
$A_{R}\cap((R\cup Q_{0})\times R)$ which is a contradiction to the fact that
$A_{R}$ is suitable for $\langle Q,A_{Q}\rangle$. Consequently, there is no
directed cycle in $D$.

It remains to show that $S$ is a dissociation set of $\mathcal{M}(D)$. That
is, we show that every $v\in N$ has degree at most one in
$G:=\mathcal{M}(D)-S$.

If $v\in Q_{1}$, then $v$ has degree one in $\mathcal{M}(D_{Q})-S$. Since no
arc in $A_{R}$ is incident with $v$, we conclude $\deg_{G}(v)=1$.

Otherwise, $v\in Q_{0}\cup R$. Then, there is no arc in $A_{Q}$ connecting $v$
with a vertex in $N\setminus S$. Moreover, by Definition 4, there is at most
one arc in $A_{R}\cap((R\cup Q_{0})\times R)$ that is incident with $v$. To
prove $\deg_{G}(v)\leq 1$ it remains to show that there is no moral edge of
$\mathcal{M}(D)$ connecting $v$ with some other vertex in $N\setminus S$.
Assume towards a contradiction that there exists some $v^{\prime}\in
N\setminus S$ such that $v$ and $v^{\prime}$ have a common child $w$.

If $w\in S\cup Q$, then $v\in Q_{0}$ and $v^{\prime}\in Q$. Consequently,
$\\{v,v^{\prime}\\}$ is a moral edge in $\mathcal{M}(D_{Q})$ which contradicts
the fact that vertices in $Q_{0}$ have degree zero in $\mathcal{M}(D_{Q})-S$.
Hence, we conclude $w\in R$ and therefore $(v,w),(v^{\prime},w)\in A_{R}$.
Then, $w$ has two incident arcs in $A_{R}\cap((R\cup Q_{0})\times R)$ which
contradicts the fact that $A_{R}$ is suitable for $\langle Q,A_{Q}\rangle$.
Hence, $\deg_{G}(v)\leq 1$. $\hfill\Box$ ■

Conversely, the arc set of every DAG whose moralized graph has a dissociation
set $S$ can be partitioned into the arc set of an ancestor tuple for $S$ and a
suitable arc set

###### Proposition 6

Let $D=(N,A)$ be a DAG, let $S\subseteq N$ be a dissociation set of
$\mathcal{M}(D)$. Then, $\langle Q,A_{Q}\rangle$ defined by

$\displaystyle Q$ $\displaystyle:=\\{v\in N\setminus S\mid v\text{ has
descendants in }S\\},$ $\displaystyle A_{Q}$ $\displaystyle:=(S\cup
Q)\times(S\cup Q)\cap A,$

is an ancestor tuple of $S$ with $|Q|\leq 2|S|$ and $A\setminus A_{Q}$ is
suitable for $\langle Q,A_{Q}\rangle$.

###### Proof

Note that Proposition 2 implies $|Q|\leq 2|S|$. We first show that Conditions
$a)$-$c)$ from Definition 3 hold for $\langle Q,A_{Q}\rangle$. Since $D=(N,A)$
is a DAG, $S\cup Q\subseteq N$, and $A_{Q}\subseteq A$, it clearly holds that
$D_{Q}$ is a DAG and therefore Condition $a)$ holds. Moreover, Condition $b)$
follows directly from the definition of $Q$ and $A_{Q}$. Condition $c)$
follows from the fact that $S$ is a dissociation set of $\mathcal{M}(D)$.

It remains to show that $A\setminus A_{Q}$ is suitable for $\langle
Q,A_{Q}\rangle$. To this end, we first show $A\setminus A_{Q}\subseteq(S\cup
Q_{0}\cup R)\times R$. Assume towards a contradiction that $A\setminus
A_{Q}\not\subseteq(S\cup Q_{0}\cup R)\times R$. Consider the following cases.

Case 1: There exists an arc $(v,w)\in A\setminus A_{Q}$ with $w\not\in R$.
Then, $w\in S\cup Q$ and therefore, $v$ is an ancestor of $S$. Hence,
$(v,w)\in A_{Q}$ which contradicts the choice of $(v,w)$.

Case 2: There exists an arc $(v,w)\in A\setminus A_{Q}$ with $v\in Q_{1}$.
From the previous case we know $w\in R$. Since $v$ has degree one in
$\mathcal{M}((N,A_{Q}))-S$ and an incident arc to some vertex in $R$ we
conclude $\deg_{\mathcal{M}(D)-S}(v)\geq 2$ which contradicts the fact that
$S$ is a dissociation set of $\mathcal{M}(D)$. Since both cases are
contradictory, it follows $A\setminus A_{Q}\subseteq(S\cup Q_{0}\cup R)\times
R$.

Finally, we show that Definition 4 holds for $A\setminus A_{Q}$. Since $D$ is
a DAG we conclude that $A\setminus A_{Q}$ contains no self-loops. Moreover,
since $S$ is a dissociation set of $\mathcal{M}(D)$ we conclude that every
$w\in(Q_{0}\cup R)$ has at most one incident edge in $(A\setminus
A_{Q})\cap((R\cup Q_{0})\times R)$. $\hfill\Box$ ■

$Q$$Q_{0}$$Q_{1}$$S$$R$ Figure 1: A DAG $D$ whose moralized graph has a
dissociation set $S$. The arc set of $D$ is decomposed into the arc set of an
ancestor tuple $\langle Q,A_{Q}\rangle$ and a suitable arc set $A_{R}$. The
thin arrows correspond to the arcs of $A_{Q}$ and the thick arrows correspond
to the arcs of $A_{R}$. The dotted edges are the moral edges.

Figure 1 shows a DAG $D$, where the arcs are decomposed into the arcs of an
ancestor tuple and a suitable arc set.

Next, we use ancestor tuples and suitable arc sets to decompose the local
scores in $(\Pi_{1}+v)$-BNSL. Let $(N,\mathcal{F},t,k)$ be an instance of
$(\Pi_{1}+v)$-BNSL and let $S\subseteq N$. Furthermore, let $\langle
Q,A_{Q}\rangle$ be an ancestor tuple for $S$ and let $A_{R}$ be suitable for
$\langle Q,A_{Q}\rangle$. Then, we set $A:=A_{Q}\cup A_{R}$ and by Proposition
5, $D:=(N,A)$ is a DAG and $S$ is a dissociation set of $\mathcal{M}(D)$.
Observe that all arcs in $A_{R}$ have endpoints in $R$ and all arcs in $A_{Q}$
have endpoints in $Q\cup S$. Hence, for every $v\in N$ it holds that either
all incoming arcs are in $A_{Q}$ or in $A_{R}$. Hence, the score of $A$ under
$\mathcal{F}$ is

$\displaystyle\sum_{v\in N}f_{v}(P_{v}^{A})=\sum_{v\in S\cup
Q}f_{v}(P_{v}^{A_{Q}})+\sum_{v\in R}f_{v}(P_{v}^{A_{R}}).$

We next show that, if $S$ and $\langle Q,A_{Q}\rangle$ are given, we can find
$A_{R}$ in polynomial time. More precisely, we solve the following problem.

$(\Pi_{1}+v)$-BNSL-Completion
Input: A set of vertices $N$, a subset $S\subseteq N$, an ancestor tuple
$\langle Q,A_{Q}\rangle$ for $S$, local scores $\mathcal{F}=\\{f_{v}\mid v\in
N\\}$, and an integer $t$.

Question: Is there an arc-set $A_{R}$ that is suitable for $\langle
Q,A_{Q}\rangle$ such that $\sum_{v\in R}f_{v}(P_{v}^{A_{R}})\geq t$?

###### Proposition 7

$(\Pi_{1}+v)$-BNSL-Completion can be solved in
$\mathcal{O}(n^{2}\cdot(n\delta_{\mathcal{F}}+\sqrt{n}))$ time.

###### Proof

We give a polynomial-time reduction to Maximum Weight Matching. In Maximum
Weight Matching one is given a graph $G=(V,E)$, edge-weights
$\omega:E\rightarrow\mathds{N}$, and $\ell\in\mathds{N}$ and the question is
if there exists a set $M\subseteq E$ of pairwise non-incident edges such that
$\sum_{e\in M}\omega(e)\geq\ell$.

Construction: Let $I:=(N,S,\langle Q,A_{Q}\rangle,\mathcal{F},t)$ be an
instance of $(\Pi_{1}+v)$-BNSL-Completion. We construct an equivalent instance
$(G,\omega,\ell)$ of Maximum Weight Matching. We first define $G:=(V,E)$ with
$V:=Q_{0}\cup R\cup R^{\prime}$, where $R^{\prime}:=\\{v^{\prime}\mid v\in
R\\}$, and $E:=X\cup Y\cup Z$, where

$\displaystyle X$ $\displaystyle:=\\{\\{v,w\\}\mid v,w\in R,v\neq w\\},$
$\displaystyle Y$ $\displaystyle:=\\{\\{v,w\\}\mid v\in R,w\in Q_{0}\\},\text{
and}$ $\displaystyle Z$ $\displaystyle:=\\{\\{v,v^{\prime}\\}\mid v\in R\\}.$

Next, we define edge-weights $\omega:E\rightarrow\mathds{N}$: For
$e=\\{v,v^{\prime}\\}\in Z$, we set $\omega(e):=\max_{S^{\prime}\subseteq
S}f_{v}(S^{\prime})$. Furthermore, for $e=\\{v,w\\}\in Y$ with $v\in R$ and
$w\in Q_{0}$, we set $\omega(e):=\max_{S^{\prime}\subseteq
S}f_{v}(S^{\prime}\cup\\{w\\})$. Finally, for $e=\\{v,w\\}\in X$, we set
$\omega(e):=\max(\varphi(v,w),\varphi(w,v))$, where

$\displaystyle\varphi(u_{1},u_{2}):=$ $\displaystyle\max_{S^{\prime}\subseteq
S}f_{u_{1}}(S^{\prime}\cup\\{u_{2}\\})$
$\displaystyle+\max_{S^{\prime}\subseteq S}f_{u_{2}}(S^{\prime}).$

To complete the construction of $(G,\omega,\ell)$, we set $\ell:=t$.

Intuition: Before we prove the correctness of the reduction we provide some
intuition. A maximum weight matching $M$ in $G$ corresponds to the parent sets
of vertices in $R$ and therefore to arcs in $A_{R}$. An edge
$\\{v,v^{\prime}\\}\in Z$ with $v\in R$ corresponds to a parent set of $v$
that contains only vertices from $S$. Moreover, an edge $\\{v,w\\}\in Y$ with
$v\in R$ corresponds to a parent set of $v$ that contains $w\in Q_{0}$ and
vertices from $S$. Finally, an edge $\\{v,w\\}\in X$ means that either $v\in
P^{A_{R}}_{w}$ or $w\in P^{A_{R}}_{v}$. Since $M$ is a matching, the
corresponding arc set is suitable for $\langle Q,A_{Q}\rangle$.

Correctness: $(\Rightarrow)$ Let $A_{R}$ be suitable for $\langle
Q,A_{Q}\rangle$ and $\sum_{v\in R}f_{v}(P_{v}^{A_{R}})\geq t$. We define a
matching $M$ with $\sum_{e\in M}\omega(e)\geq t$. To this end, we describe
which edges of $X$, $Y$, and $Z$ we add to $M$ by defining sets $M_{X}$,
$M_{Y}$, and $M_{Z}$ and set $M:=M_{X}\cup M_{Y}\cup M_{Z}$.

First, for every pair $v,w\in R$ with $v\in P^{A_{R}}_{w}$ or $w\in
P^{A_{R}}_{v}$, we add $\\{v,w\\}\in X$ to $M_{X}$. Second, for every pair
$v,w$ with $v\in R$, $w\in Q_{0}$, and $w\in P^{A_{R}}_{v}$, we add
$\\{v,w\\}$ to $M_{Y}$. Third, for every $v\in R$ that is not incident with
one of the edges in $M_{X}\cup M_{Y}$, we add $\\{v,v^{\prime}\\}$ to $M_{Z}$.
Obviously, $M_{X}$, $M_{Y}$, and $M_{Z}$ are pairwise disjoint.

We first show that $M$ is a matching by proving that there is no pair of
distinct edges in $M$ that share an endpoint. Consider the following cases.

Case 1: $e_{1},e_{2}\in M_{Z}$. Then, if $e_{1},e_{2}$ share one endpoint
$v\in R$ or $v^{\prime}\in R^{\prime}$ it follows by the definition of $M_{Z}$
that $e_{1}=e_{2}=\\{v,v^{\prime}\\}$ and therefore, there are no distinct
edges $e_{1},e_{2}\in M_{Z}$ that share exactly one endpoint.

Case 2: $e_{1},e_{2}\in M_{X}\cup M_{Y}$. Then, assume towards a contradiction
that $e_{1}=\\{u,v\\}$ and $e_{2}=\\{v,w\\}$ have a common endpoint $v$. Now,
$\\{u,v\\}\in M_{X}\cup M_{Y}$ implies $(u,v)\in A_{R}$ or $(v,u)\in A_{R}$.
Moreover $\\{v,w\\}\in M_{X}\cup M_{Y}$ implies $(w,v)\in A_{R}$ or $(v,w)\in
A_{R}$. Then, $v\in R\cup Q_{0}$ is incident with two arcs in
$A_{R}\cap((R\cup Q_{0})\times R)$ which contradicts the fact that $A_{R}$ is
suitable for $\langle Q,A_{Q}\rangle$.

Case 3: $e_{1}\in M_{X}\cup M_{Y},e_{2}\in M_{Z}$. Then, $e_{1}$ and $e_{2}$
can only have a common endpoint in $R$ which is not possible by the definition
of $M_{Z}$. We conclude that $M$ is a matching.

We next show that $\sum_{e\in M}\omega(e)\geq t$. Observe that every $v\in R$
is incident with some edge in $M$. Conversely, every edge in $M_{Y}\cup M_{Z}$
has exactly one endpoint in $R$, and every edge in $M_{X}$ has both endpoints
in $R$. Given an edge $e\in M_{Y}\cup M_{Z}$, we let $\pi(e)$ denote its
unique endpoint in $R$. By the construction of $M_{X}$ and the fact that
$A_{R}$ is suitable for $\langle Q,A_{Q}\rangle$ we know that for every
$\\{v,w\\}\in M_{X}$ it holds that either $(v,w)\in A_{R}$ or $(w,v)\in
A_{R}$. We let $\pi_{1}(e)$ and $\pi_{2}(e)$ denote the endpoints of
$e=\\{v,w\\}$ such that $(\pi_{2}(e),\pi_{1}(e))\in A_{R}$. Since every $v\in
R$ is incident with some edge in $M$ and $M$ is a matching, the following sets
form a partition of $R$.

$\displaystyle R_{1}$ $\displaystyle:=\\{\pi_{1}(e)\mid e\in M_{X}\\},$
$\displaystyle R_{2}$ $\displaystyle:=\\{\pi_{2}(e)\mid e\in M_{X}\\},$
$\displaystyle R_{3}$ $\displaystyle:=\\{\pi(e)\mid e\in M_{Y}\\},$
$\displaystyle R_{4}$ $\displaystyle:=\\{\pi(e)\mid e\in M_{Z}\\}.$

Observe that by the definitions of $M_{X},M_{Y}$, and $M_{Z}$ it holds that
all $v\in R_{2}\cup R_{4}$ have a parent set $S^{\prime}$ under $A_{R}$, where
$S^{\prime}\subseteq S$. Moreover, all $\pi(e)\in R_{3}$ have parent set
$P^{A_{R}}_{\pi(e)}=S^{\prime}\cup(e\setminus\\{\pi(e)\\})$ with
$S^{\prime}\subseteq S$, and all $\pi_{1}(e)\in R_{1}$ have parent sets
$P_{\pi_{1}(e)}^{A_{R}}=S^{\prime}\cup\\{\pi_{2}(e)\\}$ with
$S^{\prime}\subseteq S$. For the weight of $M$ it then holds that

$\displaystyle\sum_{e\in M_{X}}\omega(e)+\sum_{e\in M_{Y}}\omega(e)+\sum_{e\in
M_{Z}}\omega(e)$ $\displaystyle=$ $\displaystyle\sum_{e\in
M_{X}}\max_{S^{\prime}\subseteq
S}f_{\pi_{1}(e)}(S^{\prime}\cup\\{\pi_{2}(e)\\})$ $\displaystyle+\sum_{e\in
M_{X}}\max_{S^{\prime}\subseteq S}f_{\pi_{2}(e)}(S^{\prime})$
$\displaystyle+\sum_{e\in M_{Y}}\max_{S^{\prime}\subseteq
S}f_{\pi(e)}(S^{\prime}\cup(e\setminus\\{\pi(e)\\}))$
$\displaystyle+\sum_{e\in M_{Z}}\max_{S^{\prime}\subseteq
S}f_{\pi(e)}(S^{\prime})$ $\displaystyle\geq$ $\displaystyle\sum_{v\in
R_{1}\cup R_{2}\cup R_{3}\cup R_{4}}f_{v}(P^{A_{R}}_{v})\geq t,$

and therefore $\sum_{e\in M}\omega(e)\geq t$.

$(\Leftarrow)$ Conversely, let $M\subseteq E$ be a matching of $G$ with
$\sum_{e\in M}\omega(e)\geq t$. Note that in $G$, every $e\in E$ has at least
one endpoint in $R$ and consequently every $e\in M$ has at least one endpoint
in $R$. Moreover, without loss of generality we can assume that every vertex
of $R$ is incident with an edge of $M$: If one vertex $v\in R$ is not incident
with an edge of $M$, we replace $M$ by
$M^{\prime}:=M\cup\\{\\{v,v^{\prime}\\}\\}$. Then, $\sum_{e\in
M^{\prime}}\omega(e)\geq t+\omega(\\{v,v^{\prime}\\})\geq t$ and $M^{\prime}$
is still a matching since $\deg_{G}(v^{\prime})=1$.

We define a set $A_{R}\subseteq(S\cup Q_{0}\cup R)\times R$ and show that
$\sum_{v\in R}f_{v}(P^{A_{R}}_{v})\geq t$ and that $A_{R}$ is suitable for
$\langle Q,A_{Q}\rangle$. To this end, we define a parent set with vertices in
$S\cup Q_{0}\cup R$ for every $v\in R$. First, if $v$ is incident with an edge
$\\{v,v^{\prime}\\}\in M\cap Z$, we set
$P^{A_{R}}_{v}:=\operatorname*{\arg\\!\max}_{S^{\prime}\subseteq
S}f_{v}(S^{\prime})$. Second, if $v$ is incident with an edge $\\{v,w\\}\in
M\cap Y$, then $w\in Q_{0}$ and we set
$P^{A_{R}}_{v}:=\\{w\\}\cup\operatorname*{\arg\\!\max}_{S^{\prime}\subseteq
S}f_{v}(S^{\prime}\cup\\{w\\})$. Third, it remains to define the parent sets
of vertices in $R$ that are endpoints of some edge in $M\cap X$. Let
$\\{v,w\\}\in M\cap X$, where $\varphi(v,w)\geq\varphi(w,v)$. We then set
$P^{A_{R}}_{v}:=\\{w\\}\cup\operatorname*{\arg\\!\max}_{S^{\prime}\subseteq
S}f_{v}(S^{\prime}\cup\\{w\\})$ and we set
$P^{A_{R}}_{w}:=\operatorname*{\arg\\!\max}_{S^{\prime}\subseteq
S}f_{w}(S^{\prime})$.

We first show that $A_{R}$ is suitable for $\langle Q,A_{Q}\rangle$.
Obviously, $A_{R}$ does not contain self-loops and no $v\in R$ has a parent in
$Q_{1}$. It remains to show that every vertex in $Q_{0}\cup R$ has at most one
incident arc in $A_{R}\cap((R\cup Q_{0})\times R)$. Let $v\in Q_{0}\cup R$.
Assume towards a contradiction that $v$ is incident with two distinct arcs in
$A_{R}\cap((R\cup Q_{0})\times R)$. Then, there exists a vertex $w_{1}\in
Q_{0}\cup R$ with $(v,w_{1})\in A_{R}$ or $(w_{1},v)\in A_{R}$. Moreover,
there exists a vertex $w_{2}\in(Q_{0}\cup R)\setminus\\{w_{1}\\}$ with
$(w_{2},v)\in A_{R}$ or $(v,w_{2})\in A_{R}$. Then, by the definition of
$A_{R}$ we conclude $\\{v,w_{1}\\},\\{v,w_{2}\\}\in M$ which contradicts the
fact that no two edges in $M$ share one endpoint. We conclude that $A_{R}$ is
suitable for $\langle Q,A_{Q}\rangle$.

It remains to show that $\sum_{v\in R}f_{v}(P^{A_{R}}_{v})\geq t$. To this end
consider the following claim.

###### Claim 1

  1. a)

If $\\{v,w\\}\in M\cap(Y\cup Z)$ with $v\in R$, then
$\omega(\\{v,w\\})=f_{v}(P_{v}^{A_{R}})$.

  2. b)

If $\\{v,w\\}\in M\cap X$, then
$\omega(\\{v,w\\})=f_{v}(P_{v}^{A_{R}})+f_{w}(P_{w}^{A_{R}})$.

###### Proof

$a)$ If $\\{v,w\\}\in M\cap Z$, then $w=v^{\prime}$ and it follows by the
definition of $A_{R}$ that $f_{v}(P_{v}^{A_{R}})=\max_{S^{\prime}\subseteq
S}f_{v}(S^{\prime})=\omega(\\{v,v^{\prime}\\})$. Otherwise, if $\\{v,w\\}\in
M\cap Y$, then $w\in Q_{0}$ and analogously
$f_{v}(P_{v}^{A_{R}})=\max_{S^{\prime}\subseteq
S}f_{v}(S^{\prime}\cup\\{w\\})=\omega(\\{v,w\\})$.

$b)$ If $\\{v,w\\}\in M\cap X$, then $v,w\in R$. We only consider the case
$\varphi(v,w)\geq\varphi(w,v)$, since the other case is analogue. It then
follows from the definition of $A_{R}$, that
$f_{v}(P_{v}^{A_{R}})+f_{w}(P_{w}^{A_{R}})=\max_{S^{\prime}\subseteq
S}f_{v}(S^{\prime}\cup\\{w\\})+\max_{S^{\prime}\subseteq
S}f_{w}(S^{\prime})=\max(\varphi(v,w),\varphi(w,v))=\omega(\\{v,w\\})$.
$\hfill\Diamond$ ■

Now, let $\tilde{R}\subseteq R$ be the set of vertices in $R$ that are
incident with an edge in $M\cap X$. We conclude by Claim 1 and the assumption
that every $v\in R$ is incident with an edge in $M$ that

$\displaystyle\sum_{v\in R}f_{v}(P^{A_{R}}_{v})$ $\displaystyle=\sum_{v\in
R\setminus\tilde{R}}f_{v}(P^{A_{R}}_{v})+\sum_{v\in\tilde{R}}f_{v}(P^{A_{R}}_{v})$
$\displaystyle=\sum_{e\in M\cap(Y\cup Z)}\omega(e)+\sum_{e\in M\cap
X}\omega(e)$ $\displaystyle=\sum_{e\in M}\omega(e)\geq t,$

which completes the correctness proof.

Running Time. We now show that the reduction described above implies that
$(\Pi_{1}+v)$-BNSL-Completion can be solved in
$\mathcal{O}(n^{2}\cdot(n\delta_{\mathcal{F}}+\sqrt{n}))$ time. Obviously, the
constructed instance of Maximum Weight Matching contains $\mathcal{O}(n)$
vertices and $\mathcal{O}(n^{2})$ edges. For each edge $e$, the edge weight
$\omega(e)$ can be computed in $\mathcal{O}(n\delta_{\mathcal{F}})$ time.
Hence, we can compute the described instance of Maximum Weight Matching from
an instance of $(\Pi_{1}+v)$-BNSL-Completion in
$\mathcal{O}(n^{3}\delta_{\mathcal{F}})$ time. Together with the fact that
Maximum Weight Matching can be solved in $\mathcal{O}(\sqrt{|V|}\cdot|E|)$
time Micali and Vazirani (1980), we conclude that $(\Pi_{1}+v)$-BNSL-
Completion can be solved in
$\mathcal{O}(n^{2}\cdot(n\delta_{\mathcal{F}}+\sqrt{n}))$ time. $\hfill\Box$ ■

We can now prove that $(\Pi_{1}+v)$-BNSL can be solved in polynomial time for
constant values of $k$.

###### Theorem 8

$(\Pi_{1}+v)$-BNSL can be solved in
$\mathcal{O}((n\delta_{\mathcal{F}})^{3k}\cdot\text{{poly}}(|I|))$ time.

###### Proof

We describe the steps of the algorithm. Let $I=(N,\mathcal{F},t,k)$ be an
instance of $(\Pi_{1}+v)$-BNSL.

  1. 1.

Iterate over all possible choices for $S$ and $\langle Q,A_{Q}\rangle$ where
$|S|\leq k$ and $|Q|\leq 2k$.

  2. 2.

For each choice of $S$ and $\langle Q,A_{Q}\rangle$, let
$t^{\prime}:=t-\sum_{v\in S\cup Q}f_{v}(P_{v}^{A_{Q}})$ and check if
$(N,S,\langle Q,A_{Q}\rangle,\mathcal{F},t^{\prime})$ is a yes-instance of
$(\Pi_{1}+v)$-BNSL-Completion. In this case return _yes_.

  3. 3.

If for none of the choices of $S$ and $\langle Q,A_{Q}\rangle$ the answer
_yes_ was returned in Step 2, then return  _no_.

First, we bound the running time of the algorithm: Since $|S|\leq k$ and
$|Q|\leq 2k$, there are at most
$\binom{n}{k}\cdot\binom{n-k}{2k}\in\mathcal{O}(n^{(3k)})$ choices for $S$ and
$Q$ and $\mathcal{O}({\delta_{\mathcal{F}}}^{(3k)})$ choices for $A_{Q}$.
Hence, we can iterate over all possible choices for $S$ and $\langle
Q,A_{Q}\rangle$ in $\mathcal{O}((n\delta_{\mathcal{F}})^{(3k)})$ time.
Afterwards, for each choice of $S$ and $\langle Q,A_{Q}\rangle$ we can perform
Step 2 in $\text{{poly}}(|N|+|\mathcal{F}|)$ time due to Proposition 7.

Second, we show the correctness of the algorithm by proving that the algorithm
returns yes if and only if $(N,\mathcal{F},t,k)$ is a yes-instance of
$(\Pi_{1}+v)$-BNSL.

$(\Rightarrow)$ Let the algorithm return yes for an instance
$(N,\mathcal{F},t,k)$. Then, there exists a set $S$ of size at most $k$, an
ancestor tuple $\langle Q,A_{Q}\rangle$ for $S$, and an arc-set $A_{R}$ that
is suitable for $\langle Q,A_{Q}\rangle$. Moreover, it holds that $\sum_{v\in
S\cup Q}f_{v}(P_{v}^{A_{Q}})+\sum_{v\in R}f_{v}(P_{v}^{A_{R}})\geq t$. Then,
by Proposition 5 the graph $(N,A_{Q}\cup A_{R})$ is a DAG whose moralized
graph has dissociation set $S$ and its score is the sum of the local scores
for $A_{R}$ and $A_{Q}$ as discussed above. Hence, $(N,\mathcal{F},t,k)$ is a
yes-instance.

$(\Leftarrow)$ Conversely, let $(N,\mathcal{F},t,k)$ be a yes-instance. Then
there exists an $(N,\mathcal{F},t)$-valid DAG $D=(N,A)$ whose moralized graph
has a dissociation set $S$ of size at most $k$. Then, by Proposition 6, the
arc-set $A$ can be partitioned into $A_{Q}$ and $A_{R}$ such that there exists
some $Q\subseteq N$ and $\langle Q,A_{Q}\rangle$ is an ancestor tuple for $S$
and $A_{R}$ is suitable for $\langle Q,A_{Q}\rangle$. Since the algorithm
iterates over all possible choices for $S$ and ancestor tuples of $S$, it
considers $S$ and $\langle Q,A_{Q}\rangle$ at some point. Since $A$ is
$(N,\mathcal{F},t)$-valid, the arc-set $A_{R}$ satisfies $\sum_{v\in
R}f_{v}(P^{A_{R}}_{v})\geq t-\sum_{v\in S\cup Q}f_{v}(P_{v}^{A_{Q}})$. Hence,
the algorithm returns yes in Step 2. $\hfill\Box$ ■

Note that in a Bayesian network whose moralized graph has a dissociation set
of size $k$ the maximum parent set size is $k+1$. Otherwise, the moralized
graph has a clique of size at least $k+3$, contradicting the fact that it has
a dissociation set of size $k$. Hence, we can delete every triple
$(f_{v}(P),|P|,P)$ with $|P|>k+1$ from $\mathcal{F}$. Afterwards,
$\delta_{\mathcal{F}}\leq\binom{n}{k+1}$. Theorem 8 then implies the
following.

###### Corollary 9

$(\Pi_{1}+v)$-BNSL can be solved in
$n^{\mathcal{O}(k^{2})}+\text{{poly}}(|I|)$ time.

###  3.2 Hardness Results

We complement the algorithm for $(\Pi_{1}+v)$-BNSL by several hardness
results. First, there is little hope to obtain an FPT algorithm for
$(\Pi_{1}+v)$-BNSL parameterized by $k+t$ since the problem is W[1]-hard.
Observe that this is not implied by the W[1]-hardness of Bounded-vc-BNSL since
$(\Pi_{1}+v)$-BNSL is a different problem where we aim to find a Bayesian
network with different restrictions. However, the proof is closely related to
the W[1]-hardness-proof for Bounded-vc-BNSL Korhonen and Parviainen (2015). We
provide it here for sake of completeness.

###### Proposition 10

$(\Pi_{1}+v)$-BNSL is W[1]-hard for $k+t$, even when the superstructure
$S_{\vec{\mathcal{F}}}$ is a DAG and the maximum parent set size is three.

###### Proof

We give a parameterized reduction from Clique. In Clique we are given an
undirected graph $G=(V,E)$ and an integer $\ell$ and the question is if there
exists a subset $K\subseteq V$ of size $\ell$ such that the vertices in $K$
are pairwise adjacent in $G$. Clique is W[1]-hard if parameterized by $\ell$
Downey and Fellows (1995). Let $(G=(V,E),\ell)$ be an instance of Clique. We
describe how to construct an equivalent instance of $(\Pi_{1}+v)$-BNSL where
$k+t\in\mathcal{O}(\ell^{2})$.

Construction. We first define the vertex set $N$ by
$N:=V\cup(E\times\\{1\\})\cup(E\times\\{2\\})$. We write $e_{i}:=(e,i)$ for
the elements in $E\times\\{i\\}$, $i\in\\{1,2\\}$. Next, we define the local
scores $\mathcal{F}$. For every edge $e=\\{u,v\\}\in E$ we set
$f_{e_{1}}(\\{e_{2},u,v\\}):=1$. All other local scores are set to $0$.
Finally, we set $t:=\binom{\ell}{2}$ and $k:=\ell$. Note that
$k+t\in\mathcal{O}(\ell^{2})$ and that the maximum parent set size is three.
Moreover, in the superstructure $S_{\vec{\mathcal{F}}}$, the vertices in
$E\times\\{1\\}$ are the only vertices that have incoming arcs, and all
vertices in $E\times\\{1\\}$ are sinks. Hence, $S_{\vec{\mathcal{F}}}$ is a
DAG.

Correctness. We next show that there is a clique of size $k$ in $G$ if and
only if there exists an $(N,\mathcal{F},t)$-valid arc-set $A$ such that
$\mathcal{M}((N,A))$ has a dissociation set of size at most $k$.

$(\Rightarrow)$ Let $K$ be a clique of size $\ell$ in $G$. We then define
$A:=\\{(e_{2},e_{1}),(u,e_{1}),(v,e_{1})\mid e=\\{u,v\\}\text{ with }u,v\in
K\\}$. We prove that $A$ is $(N,\mathcal{F},t)$-valid and $\mathcal{M}(D)$ for
$D:=(N,A)$ has a dissociation set of size at most $k$.

From the fact that $S_{\vec{\mathcal{F}}}$ is a DAG, we conclude that $D$ is a
DAG. Moreover, since the vertices of $K$ are pairwise adjacent in $G$, it
follows by the construction of $\mathcal{F}$ that $f_{e_{1}}(P^{A}_{e_{1}})=1$
for all $e\in E_{G}(K)$. Since $|K|=\ell$ we conclude $\sum_{v\in
N}f_{v}(P^{A}_{v})=\binom{\ell}{2}=t$. Hence, $A$ is
$(N,\mathcal{F},t)$-valid.

Next, we show that $K$ is a dissociation set of size $k$ in $\mathcal{M}(D)$.
Observe that the vertices $e_{1}\in N$ with $e\in E_{G}(K)$ are the only
vertices that have a non-empty parent set in $D$. Hence, the moralized graph
is $\mathcal{M}(D)=(N,E_{\mathcal{M}})$, where

$E_{\mathcal{M}}=\bigcup_{e:=\\{u,v\\}\in E_{G}(K)}\\{\\{w_{1},w_{2}\\}\mid
w_{1},w_{2}\in\\{u,v,e_{1},e_{2}\\}\\}.$

It follows that $\mathcal{M}(D)-K=(N\setminus K,E_{\mathcal{M}}^{\prime})$
with

$E_{\mathcal{M}}^{\prime}=\bigcup_{e\in E_{G}(K)}\\{\\{e_{1},e_{2}\\}\\}.$

Therefore, the maximum degree in $\mathcal{M}(D)-K$ is at most one.

$(\Leftarrow)$ Conversely, let $A$ be an $(N,\mathcal{F},t)$-valid arc set
such that the moralized graph $\mathcal{M}(D)$, where $D:=(N,A)$, has a
dissociation set $S$ of size at most $k$. We prove that there is a clique of
size $k$ in $G$.

Since $A$ is $(N,\mathcal{F},t)$-valid, we know that $\sum_{v\in
N}f_{v}(P^{A}_{v})\geq\binom{k}{2}$. Together with the definition of
$\mathcal{F}$ it follows that there are at least $\binom{k}{2}$ vertices
$e_{1}\in N$ such that $P_{e_{1}}^{A}=\\{e_{2},u,v\\}$ with $\\{u,v\\}=e$. Let
$X\subseteq N$ be the set of these vertices $e_{1}$. Note that
$|X|\geq\binom{k}{2}$ and recall that for every $e_{1}\in X$ it holds that $e$
is an edge of $G$.

For every $e_{1}\in X$ with $e=\\{u,v\\}$ the set $\\{e_{1},e_{2},u,v\\}$ is a
clique of size four in $\mathcal{M}(D)$. Since $S$ is a dissociation set in
$\mathcal{M}(D)$, at least two vertices from each set $\\{e_{1},e_{2},u,v\\}$
belong to $S$. We may assume that these vertices are $u$ and $v$ by a simple
exchange argument.

Now, consider $S\cap V$. Since for every $e_{1}\in X$ with $e=\\{u,v\\}$ the
vertices $u$ and $v$ belong to $S$, we conclude that $|E_{G}(S\cap
V)|\geq\binom{k}{2}$. Together with the fact that $|S|\leq k$ it follows that
$S\cap V$ is a set of $k$ vertices with at least $\binom{k}{2}$ edges between
them. Therefore, $S\cap V$ is a clique of size $k$ in $G$. $\hfill\Box$ ■

We next consider monotone graph classes that are related to the class
$\Pi_{1}$ of isolated edges and isolated vertices. Let $\Pi_{2}$ be the class
of graphs that have maximum degree two, and let $\Pi_{3}^{\text{COC}}$ be the
class of graphs where each connected component has size at most three. These
graph classes are superclasses of $\Pi_{1}$, that is $\Pi_{1}\subseteq\Pi_{2}$
and $\Pi_{1}\subseteq\Pi_{3}^{\text{COC}}$. Consequently, if a graph $G$
belongs to the graph class $\Pi_{1}+kv$ for some $k\in\mathds{N}_{0}$, then
there exist $k^{\prime}\leq k$ and $k^{\prime\prime}\leq k$ such that
$G\in\Pi_{2}+k^{\prime}v$ and $G\in\Pi_{3}^{\text{COC}}+k^{\prime\prime}v$.
Moreover, observe that the treewidth of $G$ is not bigger than
$\min(k^{\prime},k^{\prime\prime})+\mathcal{O}(1)$.

With the next proposition we show that there is little hope that we can solve
$(\Pi_{2}+v)$-BNSL or $(\Pi_{3}^{\text{coc}}+v)$-BNSL in XP time when
parameterized by $k$. To prove the hardness result for $(\Pi_{2}+v)$-BNSL we
use a reduction from Hamiltonian Path. This reduction was already used to show
that BNSL is NP-hard if one adds the restriction that the resulting network
must be a directed path Meek (2001). We provide it here for sake of
completeness and to show that it is also correct for $(\Pi_{2}+v)$-BNSL.

###### Proposition 11

$(\Pi_{2}+v)$-BNSL and $(\Pi_{3}^{\text{coc}}+v)$-BNSL are NP-hard even if
$k=0$.

###### Proof

We prove the two statements of the proposition separately.

#### Hardness of $(\Pi_{2}+v)$-BNSL.

We give a polynomial-time reduction from the NP-hard Hamiltonian Path problem.
In Hamiltonian Path one is given an undirected graph $G$ and the question is
whether there exists a Hamiltonian path, that is, a path which contains every
vertex of $G$ exactly once.

Construction. Let $G=(V,E)$ be an instance of Hamiltonian Path with $n$
vertices. We describe how to construct an equivalent instance of
$(\Pi_{2}+v)$-BNSL where $k=0$. We first set $N:=V$. Next, for every $v\in N$
we set $f_{v}(\\{w\\})=1$ if $w\in N_{G}(v)$ and $f_{v}(P)=0$ for every other
$P\subseteq N\setminus\\{v\\}$. Finally, we set $t:=n-1$ and $k:=0$.

Correctness. $(\Rightarrow)$ Let $P=(v_{1},v_{2},\dots,v_{n})$ be a
Hamiltonian path in $G$. We set $A:=\\{(v_{i},v_{i+1})\mid
i\in\\{1,\dots,n-1\\}\\}$ and show that $A$ is $(N,\mathcal{F},t)$-valid and
$\mathcal{M}((N,A))$ has maximum degree two.

Since $P$ is a Hamiltonian path, no vertex appears twice on $P$. Hence,
$(N,A)$ does not contain directed cycles. Moreover, it holds that $v_{i}\in
N_{G}(v_{i-1})$ for every $i\in\\{2,\dots,n\\}$ and therefore $\sum_{v\in
N}f_{v}(P^{A}_{v})=n-1=t$. Hence, $A$ is $(N,\mathcal{F},t)$-valid. Since no
vertex has more than one parent in $(N,A)$, its moralized graph does not
contain moral edges and therefore
$\mathcal{M}((N,A))=(N,\\{\\{v_{i},v_{i+1}\\}\mid i\in\\{1,\dots,n-1\\}\\})$.
Consequently, the maximum degree of $\mathcal{M}((N,A))$ is two.

$(\Leftarrow)$ Conversely, let $A$ be an $(N,\mathcal{F},t)$-valid arc-set
such that $\mathcal{M}((N,A))$ has maximum degree two. Since $t=n-1$ and every
local score is either one or zero we conclude that $f_{v}(P^{A}_{v})=1$ for at
least $n-1$ vertices of $N$. By the construction of $\mathcal{F}$ this implies
that at least $n-1$ vertices have exactly one parent in $(N,A)$. Observe that,
whenever $f_{v}(\\{w\\})=1$ or $f_{w}(\\{v\\})=1$ for some $v,w\in N$, it
holds that $\\{v,w\\}$ is an edge of $\mathcal{M}((N,A))$. Furthermore, since
$\mathcal{M}((N,A))$ has maximum degree two, there is no vertex that has three
or more children. We next show that there is a Hamiltonian path $P$ in $G$. To
this end, consider the following case distinction.

Case 1: There is no vertex that has two children in $(N,A)$. Then, since at
least $n-1$ vertices have exactly one parent there exists a directed path
$P:=(v_{1},v_{2},\dots,v_{n})$ on all vertices of $N$. Since
$f_{v_{i}}(\\{v_{i+1}\\})=1$ for all $i\in\\{2,\dots,n\\}$ we conclude that
$\\{v_{i-1},v_{i}\\}\in E$. Hence, $P$ is a Hamiltonian path in $G$.

Case 2: There is exactly one vertex $v$ with two children $u_{1}$ and $w_{1}$
in $(N,A)$. Then, since $\mathcal{M}((N,A))$ has maximum degree two, it
follows that $P^{A}_{v}=\emptyset$. We conclude that every vertex in
$N\setminus\\{v\\}$ has exactly one parent in $(N,A)$. Then, there exist two
directed paths $P_{1}=(v,w_{1},\dots,w_{a})$ and $P_{2}=(v,u_{1},\dots,u_{b})$
where $a+b=n-1$ and $w_{i}\neq u_{j}$ for all $i\in\\{1,\dots,a\\}$ and
$j\in\\{1,\dots,b\\}$.

We define $P:=(w_{a},w_{a-1},\dots,w_{1},v,u_{1},\dots,u_{b})$ and show that
$P$ is a Hamiltonian path in $G$. By the above, every vertex appears exactly
once on $P$. Moreover, $G$ has an edge between every pair of consecutive
vertices on $P$: All arcs of the two paths starting in $v$ have score one. By
the construction of $\mathcal{F}$, they are also edges in $G$ and therefore
$P$ is a Hamiltonian path.

Case 3: There are at least two vertices $v$ and $w$ that have two children in
$(N,A)$. We show that this case is contradictory: Observe that the condition
of the case implies that both vertices have two incident edges with their
children in $\mathcal{M}((N,A))$. Since the maximum degree of
$\mathcal{M}((N,A))$ is two it follows that $P^{A}_{v}=P^{A}_{w}=\emptyset$.
This contradicts the fact that $f_{u}(P^{A}_{u})=1$ for at least $n-1$
vertices $u\in N$.

#### Hardness of $(\Pi_{3}^{\text{coc}}+v)$-BNSL.

We give a polynomial-time reduction from the NP-hard problem Triangle Cover
Garey and Johnson (1979). In Triangle Cover one is given an undirected graph
$G=(V,E)$ and the question is whether there exists a packing $\mathcal{P}$ of
vertex-disjoint triangles such that every vertex of $G$ belongs to one
triangle of the packing. Here, we represent
$\mathcal{P}:=\\{\\{u_{i},v_{i},w_{i}\\}\mid
i\in\\{1,\dots,\frac{|V|}{3}\\}\\}$ as a partition of $V$ where every graph
$G[\\{u_{i},v_{i},w_{i}\\}]$ is a triangle.

Construction. Let $G=(V,E)$ be an instance of Triangle Cover with $n$
vertices. We describe how to construct an equivalent instance of
$(\Pi^{\text{COC}}_{3}-v)$-BNSL where $k=0$. We first set $N:=V$. Next, for
every $v\in N$ we set $f_{v}(\\{w\\})=1$ if $w\in N_{G}(v)$,
$f_{v}(\\{u,w\\})=n$ if $\\{u,w\\}\subseteq N_{G}(v)$, and $f_{v}(P)=0$ for
every other $P\subseteq N\setminus\\{v\\}$. Finally, we set
$t:=\frac{{n}^{2}+n}{3}$ and $k:=0$.

Correctness. $(\Rightarrow)$ Let $\mathcal{P}=\\{\\{u_{i},v_{i},w_{i}\\}\mid
i\in\\{1,\dots,\frac{n}{3}\\}\\}$ be a packing of vertex-disjoint triangles
that cover $G$. We set
$A:=\bigcup_{\\{u_{i},v_{i},w_{i}\\}\in\mathcal{P}}\\{(u_{i},v_{i}),(u_{i},w_{i}),(v_{i},w_{i})\\}$
and show that $A$ is $(N,\mathcal{F},t)$-valid and every connected component
of $\mathcal{M}((N,A))$ has size three.

Since $\\{u_{i},v_{i},w_{i}\\}\cap\\{u_{j},v_{j},w_{j}\\}=\emptyset$ for
$i\neq j$ we know that $P^{A}_{w_{i}}=\\{u_{i},v_{i}\\}$,
$P^{A}_{v_{i}}=\\{u_{i}\\}$, and $P^{A}_{u_{i}}=\emptyset$ for all
$i\in\\{1,\dots,\frac{n}{3}\\}$. We conclude that $(N,A)$ is a DAG where every
connected component has size three. Since moral edges can only connect two
vertices of the same connected component in $(N,A)$, it follows that
$\mathcal{M}((N,A))\in\Pi^{\text{COC}}_{3}$.

It remains to show that the sum of all $f_{v}(P^{A}_{v})$ is at least $t$.
Since every $G[\\{u_{i},v_{i},w_{i}\\}]$ is a triangle, it follows that
$u_{i}\in N_{G}(v_{i})$ and $\\{u_{i},v_{i}\\}\subseteq N_{G}(w_{i})$. Then,
the sum of the local scores is

$\displaystyle\sum_{v\in N}f_{v}(P^{A}_{v})$ $\displaystyle=$
$\displaystyle\sum_{\\{u_{i},v_{i},w_{i}\\}\in\mathcal{P}}(f_{v_{i}}(\\{u_{i}\\})+f_{w_{i}}(\\{u_{i},v_{i}\\}))$
$\displaystyle=$
$\displaystyle\sum_{\\{u_{i},v_{i},w_{i}\\}\in\mathcal{P}}(1+n)=\frac{n^{2}+n}{3}=t.$

$(\Leftarrow)$ Conversely, let $A$ be an $(N,\mathcal{F},t)$-valid arc-set
such that every connected component of $\mathcal{M}((N,A))$ has size at most
three. Since $t=\frac{n^{2}+n}{3}$ and the local scores are either $n$ or $1$,
there are at least $\frac{n}{3}$ vertices $w_{1},w_{2},\dots,w_{\frac{n}{3}}$
that have local score $f_{w_{i}}(P^{A}_{w_{i}})=n$. Note that
$|P^{A}_{w_{i}}|=2$ due to the construction of $\mathcal{F}$. For given
$i\in\\{1,\dots,\frac{n}{3}\\}$ let $u_{i}$ and $v_{i}$ be the parents of
$w_{i}$.We now define $\mathcal{P}=\\{\\{u_{i},v_{i},w_{i}\\}\mid
i\in\\{1,\dots,\frac{n}{3}\\}\\}$ and show that $\mathcal{P}$ is a packing of
vertex-disjoint triangles for $G$. From the fact that every connected
component in $\mathcal{M}((N,A))$ has size at most three we conclude that
$\\{u_{i},v_{i},w_{i}\\}\cap\\{u_{j},v_{j},w_{j}\\}=\emptyset$ for all $i\neq
j$. This also implies that every vertex of $G$ is covered by $\mathcal{P}$
since $|\mathcal{P}|=\frac{n}{3}$ and $N=V$.

Let $i\in\\{1,\dots,\frac{n}{3}\\}$. It remains to show that
$G[\\{u_{i},v_{i},w_{i}\\}]$ is a triangle. Since
$f_{w_{i}}(\\{u_{i},v_{i}\\})=n$, it follows from the construction of
$\mathcal{F}$ that $\\{u_{i},w_{i}\\}\in E$ and $\\{v_{i},w_{i}\\}\in E$.
Next, observe that in each component $\\{u_{i},v_{i},w_{i}\\}$ the only
further arc besides $(u_{i},w_{i})$ and $(v_{i},w_{i})$ is either
$(v_{i},u_{i})$ or $(u_{i},v_{i})$ and therefore
$f_{u_{i}}(P^{A}_{u_{i}})+f_{v_{i}}(P^{A}_{v_{i}})+f_{w_{i}}(P^{A}_{w_{i}})\leq
n+1$. Together with the fact that $t=\frac{n^{2}+n}{3}$ it follows that
$f_{u_{i}}(P^{A}_{u_{i}})+f_{v_{i}}(P^{A}_{v_{i}})+f_{w_{i}}(P^{A}_{w_{i}})=n+1$.
Then, either $P^{A}_{u_{i}}=\\{v_{i}\\}$ or $P^{A}_{v_{i}}=\\{u_{i}\\}$ and
the construction of $\mathcal{F}$ implies $\\{u_{i},v_{i}\\}\in E$. Hence,
$G[\\{u_{i},v_{i},w_{i}\\}]$ is a triangle. $\hfill\Box$ ■

##  4 Edge Deletion Distances

###  4.1 Bounded-Edges-BNSL

We now consider a version of BNSL, where we aim to learn a network whose
moralized graph has a bounded number of edges. More precisely, we consider
$(\Pi_{0}+e)$-BNSL where $\Pi_{0}$ is the class of edgeless graphs. Clearly,
$\Pi_{0}$ is monotone. Note that, given some $k\in\mathds{N}$, a DAG $D=(N,A)$
with $\mathcal{M}(D)\in(\Pi_{0}+ke)$ is a DAG whose moralized graph contains
at most $k$ edges. Observe that there is a simple algorithm that solves
$(\Pi_{0}+e)$-BNSL in XP time when parameterized by $k$: Let
$I=(N,\mathcal{F},t,k)$ be an instance of $(\Pi_{0}+e)$-BNSL. If $(N,A)$ is
Bayesian network whose moralized graph has $k$ or less edges, we conclude
$|A|\leq k$. Hence, we can iterate over all $\mathcal{O}(n^{2k})$ possible
sets $A$ of vertex-tuples such that $|A|\leq k$. If we consider the
superstructure $S_{\vec{\mathcal{F}}}=(N,A_{\mathcal{F}})$ we can instead
iterate over all possible subsets $A^{\prime}\subseteq A_{\mathcal{F}}$ with
$|A^{\prime}|\leq k$. Afterwards, we check if $A^{\prime}$ is an
$(N,\mathcal{F},t)$-valid arc set and
$\mathcal{M}((N,A^{\prime}))\in\Pi_{0}+ke$. This implies the following.

###### Proposition 12

$(\Pi_{0}+e)$-BNSL can be solved in
$\mathcal{O}(m^{k}\cdot\text{{poly}}(|I|))$ time.

To put this into context, we show that $(\Pi_{0}+e)$-BNSL is W[1]-hard when
parameterized by $t+k$. Hence, there is little hope to solve
$(\Pi_{0}+e)$-BNSL in FPT time for $t+k$.

###### Theorem 13

$(\Pi_{0}+e)$-BNSL is W[1]-hard when parameterized by $t+k$, even when
$S_{\vec{\mathcal{F}}}$ is a DAG and the maximum parent set size is three.

###### Proof

We prove W[1]-hardness by giving a parameterized reduction from the following
problem.

Multicolored Clique
Input: A properly $\ell$-colored undirected graph $G=(V,E)$ with color classes
$C_{1},\ldots,C_{\ell}\subseteq V$.

Question: Is there a clique containing one vertex from each color in $G$?

Multicolored Clique is W[1]-hard when parameterized by $\ell$ Pietrzak (2003);
Fellows et al. (2009). Let $G=(V,E)$ be a properly $\ell$-colored undirected
graph with color classes $C_{1},\dots,C_{\ell}$. We describe how to construct
an equivalent instance $I=(N,\mathcal{F},t,k)$ of $(\Pi_{0}+e)$-BNSL from $G$.

Construction. First, we define the vertex set $N$. Every vertex $v\in V$
becomes a vertex in $N$ and for every pair $\\{C_{i},C_{j}\\}$ ($i\neq j$) of
color classes we add a vertex $w_{\\{i,j\\}}$ to $N$. Let $W$ be the set of
all such vertices $w_{\\{i,j\\}}$. Moreover, we add a vertex $x$ to $N$ which
we will call the  _central vertex_ for the rest of the proof. Note that
$|N|=|V|+\binom{\ell}{2}+1\in\mathcal{O}(|V|+\ell^{2})$.

Second, we define the local scores $\mathcal{F}$. For every vertex $u\in
V\cup\\{x\\}$ we set $f_{u}(P):=0$ for every possible parent set $P$. It
remains to define the local scores for the vertices in $W$. Let
$i,j\in\\{1,\dots,\ell\\}$ with $i\neq j$. We set
$f_{w_{\\{i,j\\}}}(\\{u,v,x\\}):=1$ if there is an edge $\\{u,v\\}\in E$
connecting a vertex $u\in C_{i}$ and $v\in C_{j}$. For all other possible
parent sets $P$ we set $f_{w_{\\{i,j\\}}}(P):=0$. Observe that the value of
the local scores is either $0$ or $1$ and there are exactly $|E|$ values with
$f_{v}(P)=1$. Since we assume that local scores are given in non-zero
representation, we conclude $|\mathcal{F}|\in\mathcal{O}(|E|)$.

Finally, we set $t:=\binom{\ell}{2}$ and $k:=4\binom{\ell}{2}+\ell$. Note that
$t+k\in\mathcal{O}(\ell^{2})$. Figure 2 shows an example of the construction.

$x$$w_{\\{1,3\\}}$$w_{\\{2,3\\}}$$w_{\\{1,2\\}}$$C_{3}$$C_{1}$$C_{2}$$v_{1}$$v_{2}$$v_{3}$
Figure 2: An example of the construction given in the proof of Theorem 13. The
original instance contains a multicolored clique on the vertices $v_{1}\in
C_{1}$, $v_{2}\in C_{2}$, and $v_{3}\in C_{3}$. The directed edges represent
the arcs of a DAG with score $3$ such that the moralized graph contains $15$
edges. The dotted edges correspond to the moralized edges.

Moreover, observe that the maximum parent set size is three and the
superstructure $S_{\vec{\mathcal{F}}}$ is a DAG since every vertex in
$V\cup\\{x\\}$ has in-degree zero in $S_{\vec{\mathcal{F}}}$ and every vertex
in $W$ is a sink in $S_{\vec{\mathcal{F}}}$.

Intuition. Before we show the correctness of the reduction, we start with some
intuition. To reach the score $t=\binom{\ell}{2}$, every vertex in $W$ must
choose a parent set with score $1$. Hence, every $w_{\\{i,j\\}}$ chooses a
parent set $\\{u,v,x\\}$ with $u\in C_{i}$ and $v\in C_{j}$. This choice
represents the choice of an edge $\\{u,v\\}\in E$ between the vertices $u$ and
$v$ of a multicolored clique in $G$. Considering the moralized graph of the
resulting Bayesian network, the number moral edges that are incident with the
central vertex $x$ guarantees that the chosen edges form a multicolored clique
in the following sense: If the parent sets of vertices in $W$ do not
correspond to the edges of a multicolored clique in $G$, the moralized graph
consists of more than $k=4\binom{\ell}{2}+\ell$ edges.

Correctness. $(\Rightarrow)$ Let $S:=\\{v_{1},\dots,v_{\ell}\\}$ with
$v_{i}\in C_{i}$ be a multicolored clique in $G$. We define the arc set
$A:=\\{(v_{i},w_{\\{i,j\\}}),(v_{j},w_{\\{i,j\\}}),(x,w_{\\{i,j\\}})\mid
w_{\\{i,j\\}}\in W\\}$. We show that $A$ is $(N,\mathcal{F},t)$-valid and that
there are at most $k$ edges in $\mathcal{M}((N,A))$.

Since the vertices of $S$ are pairwise adjacent in $G$, it holds that
$f_{w_{\\{i,j\\}}}(P^{A}_{w_{\\{i,j\\}}})=1$ for every $w_{\\{i,j\\}}\in W$
and therefore $\sum_{v\in N}f_{v}(P^{A}_{v})=\binom{\ell}{2}=t$. Moreover,
since $S_{\vec{\mathcal{F}}}$ is a DAG we conclude that $(N,A)$ is a DAG.
Hence, $A$ is $(N,\mathcal{F},t)$-valid.

It remains to check that there are at most $k=4\cdot\binom{\ell}{2}+\ell$
edges in $\mathcal{M}((N,A))$. First, we consider the number of arcs in
$(N,A)$. Since every vertex in $W$ has three parents in $(N,A)$, we conclude
$|A|=3\cdot\binom{\ell}{2}$. Next, we consider the moral edges in
$\mathcal{M}((N,A))$. Let $a,b\in N$ be two vertices that have a common child
in $(N,A)$. Observe that all vertices in $V\setminus S\cup W$ have out-degree
zero in $(N,A)$. We conclude $a,b\in S\cup\\{x\\}$. Then, there are at most
$|\\{\\{a,b\\}\mid a\in S,b\in S\cup\\{x\\}\\}|=\binom{\ell}{2}+\ell$ moral
edges. Hence, there are at most $k=4\cdot\binom{\ell}{2}+\ell$ edges in
$\mathcal{M}((N,A))$.

$(\Leftarrow)$ Conversely, let $A\subseteq N\times N$ be an
$(N,\mathcal{F},t)$-valid arc set such that $\mathcal{M}((N,A))$ contains at
most $k=4\binom{\ell}{2}+\ell$ edges. We show that there exists a multicolored
clique $S$ in $G$.

Since $A$ is $(N,\mathcal{F},t)$-valid, we know that $\sum_{v\in
N}f_{v}(P^{A}_{v})=\binom{\ell}{2}$ and conclude that for every
$w_{\\{i,j\\}}\in W$ it holds that
$f_{w_{\\{i,j\\}}}(P^{A}_{w_{\\{i,j\\}}})=1$. By the construction of
$\mathcal{F}$ this implies $|P^{A}_{w_{\\{i,j\\}}}|=3$ for every
$w_{\\{i,j\\}}\in W$. We conclude $|A|=3\binom{\ell}{2}$. Hence, there are at
most $\binom{\ell}{2}+\ell$ moral edges in $\mathcal{M}((N,A))$.

Before we define the multicolored clique $S$, we take a closer look at the
moral edges that are incident with vertices of the color classes
$C_{1},\dots,C_{\ell}$. Let $C_{i}$ and $C_{j}$ be distinct color classes.
Then, since $P^{A}_{w_{\\{i,j\\}}}$ contains one vertex from $C_{i}$ and one
vertex from $C_{j}$, there exists a moral edge between the vertices of $C_{i}$
and $C_{j}$. Hence, there are at least $\binom{\ell}{2}$ moral edges between
the color classes of $C_{1},\dots,C_{\ell}$. Together with the fact that the
overall number of moral edges in $\mathcal{M}((N,A))$ is at most
$\binom{\ell}{2}+\ell$, we conclude that there are at most $\ell$ moral edges
that are incident with the central vertex $x$. We use the following claim to
define a multicolored clique $S$ in $G$.

###### Claim 2

For every color class $C_{i}$ it holds that
$|E_{\mathcal{M}((N,A))}(C_{i},\\{x\\})|=1$.

###### Proof

Let $C_{i}$ be a color class. Note that there is no arc in $A$ connecting $x$
with some vertices in $C_{i}$. So, $E_{\mathcal{M}((N,A))}(C_{i},\\{x\\})$
contains only moral edges. For every $j\in\\{1,\dots,\ell\\}$ with $j\neq i$,
the vertex $w_{\\{i,j\\}}$ has a parent set $P^{A}_{w_{\\{i,j\\}}}$ containing
some $v\in C_{i}$, $u\in C_{j}$ and $x$. Then, there exists a moral edges
$\\{u,v\\}$, $\\{v,x\\}$, and $\\{u,x\\}$. Therefore, every color class
contains a vertex that is adjacent to $x$ by a moral edge. Since there are at
most $\ell$ moral edges incident with $x$, we conclude
$|E_{\mathcal{M}((N,A))}(C_{i},\\{x\\})|=1$. $\hfill\Diamond$ ■

We next use Claim 2 to conclude that, given a color class $C_{i}$, there is
exactly one vertex $v_{i}$ that is a parent of all $w_{\\{i,j\\}}\in W$ with
$j\neq i$: Assume towards a contradiction that there are two distinct vertices
$v_{i},v_{i}^{\prime}\in C_{i}$ such that $v_{i}\in P^{A}_{w_{\\{i,j\\}}}$ and
$v_{i}^{\prime}\in P^{A}_{w_{\\{i,j^{\prime}\\}}}$ for $j\neq j^{\prime}$.
Then, since $x$ is a parent of $w_{\\{i,j\\}}$ and $w_{\\{i,j^{\prime}\\}}$,
it follows that $|E_{\mathcal{M}((N,A))}(C_{i},\\{x\\})|\geq 2$ contradicting
Claim 2.

We now define $S:=\\{v_{1},v_{2},\dots,v_{\ell}\\}$, where $v_{i}\ \in C_{i}$
is the unique vertex that is a parent of all $w_{\\{i,j\\}}\in W$ with $j\neq
i$. It remains to show that $S$ is a multicolored clique in $G$. The vertices
of $S$ are obviously elements of distinct color classes. Moreover, given
distinct vertices $v_{i},v_{j}\in S$ it holds that
$P^{A}_{w_{\\{i,j\\}}}=\\{v_{i},v_{j},x\\}$. Then, since
$f_{w_{\\{i,j\\}}}(P^{A}_{w_{\\{i,j\\}}})=1$ it follows from the construction
of $\mathcal{F}$ that there is an edge $\\{v_{i},v_{j}\\}\in E$. Hence, $S$ is
a multicolored clique in $G$. $\hfill\Box$ ■

We next use Theorem 13 to prove that learning a Bayesian network whose
moralized graph has a bounded feedback edge set is also W[1]-hard when
parameterized by the size of the _feedback edge set_. More formally, let
$\Pi_{F}$ be the class of forests, which are undirected acyclic graphs. We
show the following.

###### Theorem 14

$(\Pi_{F}+e)$-BNSL is W[1]-hard when parameterized by $k$, even when
restricted to instances where $S_{\vec{\mathcal{F}}}$ is a DAG and the maximum
parent set size is four.

###### Proof

We give a parameterized reduction from $(\Pi_{0}+e)$-BNSL parameterized by the
number of edges $k$ which is W[1]-hard even on instances where the
superstructure is a DAG and the maximum parent set size is three due to
Theorem 13.

Construction. Let $I:=(N,\mathcal{F},t,k)$ be such instance of
$(\Pi_{0}+e)$-BNSL. We describe how to construct an equivalent instance
$I^{\prime}:=(N^{\prime},\mathcal{F}^{\prime},t^{\prime},k^{\prime})$ for
$(\Pi_{F}+e)$-BNSL where $k^{\prime}=k$. To this end, let $x\not\in N$ and we
define the vertex set $N^{\prime}:=N\cup\\{x\\}$.

To define the local scores $\mathcal{F}^{\prime}$, we define the auxiliary
value $\ell^{+}:=1+\sum_{v\in N}\max_{P\subseteq N\setminus\\{v\\}}f_{v}(P)$.
For every $v\in N$ we set
$f_{v}^{\prime}(P)=f_{v}(P\setminus\\{x\\})+\ell^{+}$ if $x\in P$, and
$f_{v}^{\prime}(P)=0$ if $x\not\in P$. For $x$, we set $f_{x}^{\prime}(P)=0$
for every $P$. Finally, we set $t^{\prime}:=t+n\cdot\ell^{+}$.

We can obviously compute $I^{\prime}$ from $I$ in polynomial time. Since $I$
is an instance where $S_{\vec{\mathcal{F}}}$ is a DAG and the maximum parent
set size is three, we conclude that the maximum parent set size of
$I^{\prime}$ is four and that $S_{\vec{\mathcal{F}^{\prime}}}$ is a DAG.

Intuition. Before we prove the correctness of the reduction we provide some
intuition. To obtain an $(N^{\prime},\mathcal{F}^{\prime},t^{\prime})$ valid
arc set $A^{\prime}$, the vertex $x$ must be a parent of every vertex of $N$.
Hence, for every $v\in N$, there exists an edge $\\{x,v\\}$ in
$\mathcal{M}((N^{\prime},A^{\prime}))$. The idea is that
$\mathcal{M}((N^{\prime},A^{\prime}))$ can be transformed into an acyclic
graph by deleting all edges between the vertices of $N$.

Correctness. We now prove that $I$ is a yes-instance of $(\Pi_{0}+e)$-BNSL if
and only if $I^{\prime}$ is a yes-instance of $(\Pi_{\text{AC}}+e)$-BNSL.

$(\Rightarrow)$ Let $A\subseteq N\times N$ be an $(N,\mathcal{F},t)$-valid arc
set such that $\mathcal{M}(D)$ for $D:=(N,A)$ contains at most $k$ edges. We
then define $A^{\prime}:=A\cup\\{(x,v)\mid v\in N\\}$ and let
$D^{\prime}:=(N^{\prime},A^{\prime})$. We show that $A^{\prime}$ is
$(N^{\prime},\mathcal{F}^{\prime},t^{\prime})$-valid and
$\mathcal{M}(D^{\prime})$ has a feedback edge set of size at most $k$.

We first show that $A^{\prime}$ is
$(N^{\prime},\mathcal{F}^{\prime},t^{\prime})$-valid. Since
$S_{\vec{\mathcal{F}^{\prime}}}$ is a DAG we conclude that $D$ is a DAG.
Moreover, note that $P^{A^{\prime}}_{v}=P^{A}_{v}\cup\\{x\\}$ for every $v\in
N$ and therefore

$\displaystyle\sum_{v\in N^{\prime}}f_{v}^{\prime}(P^{A^{\prime}}_{v})$
$\displaystyle=\sum_{v\in N}(f_{v}(P^{A}_{v})+\ell^{+})$
$\displaystyle=t+n\cdot\ell^{+}=t^{\prime}.$

Consequently, $D^{\prime}$ is
$(N^{\prime},\mathcal{F}^{\prime},t^{\prime})$-valid. It remains to show that
$\mathcal{M}(D^{\prime})$ has a feedback edge set of size at most $k$. To this
end, consider the following claim.

###### Claim 3

Let $v,w\in N$. Then, $\\{v,w\\}$ is a moral edge in $\mathcal{M}(D)$ if and
only if $\\{v,w\\}$ is a moral edge in $\mathcal{M}(D^{\prime})$.

###### Proof

Let $\\{v,w\\}$ be a moral edge in $\mathcal{M}(D)$. Then, there exists a
vertex $u\in N$ such that $(v,u),(w,u)\in A$. Since $A\subseteq A^{\prime}$ we
conclude that $\\{v,w\\}$ is a moral edge in $\mathcal{M}(D^{\prime})$.

Conversely, let $\\{v,w\\}$ be a moral edge in $\mathcal{M}(D^{\prime})$.
Then, $v$ and $w$ have a common child $u$ in $D^{\prime}$. Since $x$ has no
incoming arcs, we conclude $u\in N$ and therefore $(v,u),(w,u)\in A$. Hence,
$\\{v,w\\}$ is a moral edge in $\mathcal{M}(D)$. $\hfill\Diamond$ ■

Claim 3 together with the fact that $(N\times N)\cap A^{\prime}=A$ implies
that $v,w\in N$ are adjacent in $\mathcal{M}(D)$ if and only if they are
adjacent in $\mathcal{M}(D^{\prime})$. Hence, if we delete every edge of
$\mathcal{M}(D)$ from $\mathcal{M}(D^{\prime})$ we obtain the graph
$G:=(N^{\prime},\\{\\{x,v\\}\mid v\in N\\})$ which is acyclic. Since there are
at most $k$ edges in $\mathcal{M}(D)$ we conclude that there exists a feedback
edge set of size at most $k$ for $\mathcal{M}(D^{\prime})$.

$(\Leftarrow)$ Conversely, let $A^{\prime}$ be an
$(N^{\prime},\mathcal{F}^{\prime},t^{\prime})$-valid arc-set such that
$\mathcal{M}(D^{\prime})$ for $D^{\prime}:=(N^{\prime},A^{\prime})$ has a
feedback edge set of size at most $k$. We define $A:=(N\times N)\cap
A^{\prime}$. Note that $P_{v}^{A}=P_{v}^{A^{\prime}}\setminus\\{x\\}$.

We first show that $D:=(N,A)$ is $(N,\mathcal{F},t)$-valid. Obviously, $D$ is
a DAG since $S_{\vec{\mathcal{F}}}$ is a DAG. Moreover, it holds that

$\displaystyle\sum_{v\in N}f_{v}(P^{A}_{v})$ $\displaystyle=\sum_{v\in
N}f_{v}(P^{A^{\prime}}_{v}\setminus\\{x\\})$
$\displaystyle=t^{\prime}-n\cdot\ell^{+}=t.$

Consequently, $D$ is $(N,\mathcal{F},t)$-valid. It remains to show that there
are at most $k$ edges in $\mathcal{M}(D)$. To this end, observe that $x\in
P^{A^{\prime}}_{v}$ for every $v\in N$: If there exists a vertex $w\in N$ with
$x\not\in P^{A^{\prime}}_{w}$, then $f^{\prime}_{w}(P^{A^{\prime}}_{w})=0$ and
therefore the sum of the local scores is smaller than $n\cdot\ell^{+}$. This
contradicts the fact that $A^{\prime}$ is
$(N^{\prime},\mathcal{F}^{\prime},t^{\prime})$-valid.

Next, assume towards a contradiction that there are more than $k$ edges in
$\mathcal{M}(D)$. Since $A\subseteq A^{\prime}$, this implies that in
$\mathcal{M}(D^{\prime})$ there are more than $k$ edges between the vertices
of $N$. Furthermore, since $x\in P^{A^{\prime}}(v)$ for every $v\in N$ we
conclude that every vertex in $N$ is adjacent to $x$ in
$\mathcal{M}(D^{\prime})$. Hence, $\mathcal{M}(D^{\prime})$ consists of $n+1$
vertices and at least $n+k+1$ edges which contradicts the fact that
$\mathcal{M}(D^{\prime})$ has a feedback edge set of size at most $k$.
$\hfill\Box$ ■

For efficient inference it is desirable to have a small treewidth in the
moralized graph. The size of a feedback edge set is a large upper bound for
the treewidth. Since even learning Bayesian networks under this constraint is
W[1]-hard, it appears to be unlikely to obtain fixed-parameter tractability
for natural parameters that bound the treewidth of the moralized graph.

#### Bounded-Arcs-BNSL

Next, we consider a version of Bayesian Network Structure Learning where we
want to learn a Bayesian network with a bounded number of arcs. In contrast to
$(\Pi_{0}+e)$-BNSL, the additional sparsity constraint does not affect the
moralized graph but only the arcs of the DAG itself. The problem is formally
defined as follows.

Bounded Arcs Bayesian Network Structure Learning (BA-BNSL)
Input: A set of vertices $N$, local scores $\mathcal{F}=\\{f_{v}\mid v\in
N\\}$, and two integers $t,k\in\mathds{N}$.

Question: Is there an $(N,\mathcal{F},t)$-valid arc set $A\subseteq N\times N$
such that $|A|\leq k$?

BA-BNSL is a generalization of Vanilla-BNSL and therefore NP-hard. We prove
that—in contrast to $(\Pi_{0}+e)$-BNSL—BA-BNSL becomes polynomial-time
solvable if the superstructure is a DAG. The algorithm uses dynamic
programming over a topological ordering of $S_{\vec{\mathcal{F}}}$.
Furthermore, we obtain fixed-parameter tractability for the parameter $k$. On
the negative side, we show that BA-BNSL does not admit a problem kernel of
size polynomial in $t+k$ unless $\text{\rm NP}\subseteq\text{\rm
coNP}/\text{\rm poly}$.

###### Proposition 15

BA-BNSL can be solved in $\mathcal{O}(\delta_{\mathcal{F}}\cdot k\cdot n)$
time if the superstructure $S_{\vec{\mathcal{F}}}$ is a DAG.

###### Proof

We give a simple dynamic programming algorithm. Let $N:=\\{1,\dots,n\\}$, and
let $(N,\mathcal{F},t,k)$ be an instance of BA-BNSL such that
$S_{\vec{\mathcal{F}}}$ is a DAG. Then, there exists such a topological
ordering of $S_{\vec{\mathcal{F}}}$. Without loss of generality, let
$(n,n-1,\dots,2,1)$ be such topological ordering. Hence, for every arc $(a,b)$
of $S_{\vec{\mathcal{F}}}$ it holds that $a>b$.

The dynamic programming table $T$ has entries of the type $T[i,j]$ for all
$i\in\\{0,1,\dots,n\\}$ and $j\in\\{0,1,\dots,k\\}$. Each entry stores the
maximum sum of local scores of the vertices $(i,\dots,1)$ of the topological
ordering that can be obtained by an arc set $A$ of size at most $j$. For
$i=0$, we set $T[0,j]=0$ for all $j\in\\{0,\dots,k\\}$. The recurrence to
compute an entry for $i>0$ is

$T[i,j]=\max_{P\in P_{\mathcal{F}}(i),|P|\leq
j}(f_{i}(P)+T[i-1,j-|P|])\text{,}$

and the result can then be computed by checking if $T[n,k]\geq t$. The
corresponding network can be found by traceback. The correctness proof is
straightforward and thus omitted. The size of $T$ is $\mathcal{O}(n\cdot k)$
and each entry $T[i,j]$ can be computed in $\mathcal{O}(\delta_{\mathcal{F}})$
time by iterating over the at most $\delta_{\mathcal{F}}$ triples
$(f_{i}(P),|P|,P)$ in $\mathcal{F}$ for the vertex $i$. Therefore, BA-BNSL can
be solved in $\mathcal{O}(\delta_{\mathcal{F}}\cdot k\cdot n)$ time if
$S_{\vec{\mathcal{F}}}$ is a DAG. $\hfill\Box$ ■

#### A randomized algorithm for BA-BNSL.

The dynamic programming algorithm behind Proposition 15 can be adapted to
obtain an FPT algorithm for BA-BNSL when parameterized by the number of arcs
$k$. The algorithm is based on color coding Alon et al. (1995): In a Bayesian
network with at most $k$ arcs, there are at most $2k$ vertices which are
endpoints of such arcs. The idea of color coding is to randomly color the
vertices of $N$ with $2k$ colors and find a solution $A$ where all vertices
that are incident with arcs of $A$ are colored with pairwise distinct colors.

Before we present the algorithm we provide an observation about the input
structure for BA-BNSL. This will help us to give a more detailed running-time
analysis of the algorithm. Given an instance $I:=(N,\mathcal{F},t,k)$ of BA-
BNSL, we can assume that $t\geq\sum_{v\in N}f_{v}(\emptyset)$, since otherwise
$A=\emptyset$ is a solution for $I$ and therefore, $I$ is a trivial yes-
instance.

Next, let $I$ be a yes-instance for BA-BNSL. We call a solution $A$ for $I$
_nice_ , if $f_{v}(P^{A}_{v})\leq f_{v}(\emptyset)$ implies
$P^{A}_{v}=\emptyset$. It is easy to see that for every yes-instance there
exists a nice solution $A$, since parent sets $P_{v}^{A}\neq\emptyset$ with
$f_{v}(P_{v}^{A})\leq f_{v}(\emptyset)$ can be replaced by $\emptyset$
analogously to Proposition 1. With the next proposition, we state that every
instance of BA-BNSL can be transformed in $\mathcal{O}(|\mathcal{F}|)$ time
into an equivalent instance with $f_{v}(\emptyset)=0$ for every vertex $v$ in
a preprocessing. This preprocessing helps us to improve the running-time of
the algorithm since if some value $f_{v}(\emptyset)$ is requested we do not
need to extract it from the two-dimensional array representing $\mathcal{F}$.

###### Proposition 16

Let $I:=(N,\mathcal{F},t,k)$ be an instance of BA-BNSL. Then, there exist
$\mathcal{F}^{\prime}:=\\{f_{v}^{\prime}\mid v\in N\\}$ with
$f^{\prime}_{v}(\emptyset)=0$ for every $v\in N$ and
$t^{\prime}\in\mathds{N}_{0}$, such that an arc-set $A$ is a nice solution for
$I$ if and only if $A$ is a nice solution for
$I^{\prime}:=(N,\mathcal{F}^{\prime},t^{\prime},k)$. Furthermore, $I^{\prime}$
can be computed in $\mathcal{O}(|\mathcal{F}|)$ time.

###### Proof

Let $v\in N$. We define the new local scores $f_{v}^{\prime}$ by setting
$f_{v}^{\prime}(P):=f_{v}(P)-f_{v}(\emptyset)$, if $f_{v}(P)\geq
f_{v}(\emptyset)$, and $f_{v}^{\prime}(P):=0$ otherwise. Note that
$f^{\prime}_{v}(\emptyset)=0$ for all $v\in N$. Furthermore, we set
$t^{\prime}:=t-\sum_{v\in N}f_{v}(\emptyset)$. Obviously,
$\mathcal{F}^{\prime}$ and $t^{\prime}$ can be computed in
$\mathcal{O}(|\mathcal{F}|)$ time by iterating over the two-dimensional array
representing $\mathcal{F}$. Moreover, $t^{\prime}\geq 0$ by the assumption
$t\geq\sum_{v\in N}f_{v}(\emptyset)$ discussed above. We next show that
$A\subseteq N\times N$ is a nice solution for $I$ if and only if $A$ is a nice
solution for $I^{\prime}$.

$(\Rightarrow)$ Let $A$ be a nice solution for $I$. Obviously, $(N,A)$ is a
DAG and $|A|\leq k$. Hence, it remains to show that $\sum_{v\in
N}f^{\prime}_{v}(P^{A}_{v})\geq t^{\prime}$ and that $A$ is nice for
$I^{\prime}$.

Since $A$ is nice for $I$, it holds that $f_{v}(P^{A}_{v})\geq
f_{v}(\emptyset)$ for every $v\in N$. Hence,

$\displaystyle\sum_{v\in N}f^{\prime}_{v}(P^{A}_{v})$
$\displaystyle=\sum_{v\in N}(f_{v}(P^{A}_{v})-f_{v}(\emptyset))$
$\displaystyle\geq t-\sum_{v\in N}f_{v}(\emptyset)=t^{\prime}.$

To show that $A$ is nice for $I^{\prime}$, let $f^{\prime}_{v}(P^{A}_{v})\leq
f^{\prime}_{v}(\emptyset)$. We conclude $f^{\prime}_{v}(P^{A}_{v})=0$ and
therefore $f_{v}(P^{A}_{v})\leq f_{v}(\emptyset)$. Since $A$ is nice for $I$,
we conclude $P^{A}_{v}=\emptyset$. Hence, $A$ is a nice solution for
$I^{\prime}$.

$(\Leftarrow)$ Conversely, let $A$ be nice for $I^{\prime}$. We show that $A$
is a nice solution for $I$. Obviously $(N,A)$ is a DAG and $|A|\leq k$. Hence,
it remains to show that $\sum_{v\in N}f_{v}(P^{A}_{v})\geq t$ and that $A$ is
nice for $I$.

To this end, we first show that for every $v\in N$ it holds that
$f^{\prime}_{v}(P^{A}_{v})=f_{v}(P^{A}_{v})-f_{v}(\emptyset)$. Assume towards
a contradiction that there exists some $v\in N$ such that
$f^{\prime}_{v}(P^{A}_{v})\neq f_{v}(P^{A}_{v})-f_{v}(\emptyset)$. It then
follows by the definition of $\mathcal{F}^{\prime}$, that
$f_{v}(P^{A}_{v})<f_{v}(\emptyset)$ and that $f_{v}^{\prime}(P^{A}_{v})=0$.
Note that $f_{v}^{\prime}(P^{A}_{v})=0$ implies $f_{v}^{\prime}(P^{A}_{v})\leq
f_{v}^{\prime}(\emptyset)$ and therefore $P^{A}_{v}=\emptyset$ since $A$ is
nice for $I^{\prime}$. This contradicts the fact that
$f_{v}(P^{A}_{v})<f_{v}(\emptyset)$.

Since $f^{\prime}_{v}(P^{A}_{v})=f_{v}(P^{A}_{v})-f_{v}(\emptyset)$ for every
$v\in N$ the sum of the local scores is

$\displaystyle\sum_{v\in N}f_{v}(P^{A}_{v})$ $\displaystyle=\sum_{n\in
N}(f^{\prime}_{v}(P)+f_{v}(\emptyset))$ $\displaystyle\geq
t^{\prime}+\sum_{n\in N}f_{v}(\emptyset)=t.$

To show that $A$ is nice for $I$, let $f_{v}(P^{A}_{v})\leq f_{v}(\emptyset)$.
By the construction of $\mathcal{F}$, this implies that
$f^{\prime}_{v}(P^{A}_{v})=0$ and therefore
$f^{\prime}_{v}(P^{A}_{v})=f^{\prime}_{v}(\emptyset)$. Since $A$ is nice for
$I^{\prime}$ we conclude $P^{A}_{v}=\emptyset$. Hence, $A$ is a nice solution
for $I$. $\hfill\Box$ ■

To describe the color coding algorithm, we introduce some notation. Let $N$ be
a set of vertices. A function $\chi:N\rightarrow\\{1,\dots,2k\\}$ is called a
_coloring (of $N$ with $2k$ colors)_. Given a color $c\in\\{1,\dots,2k\\}$, we
call $\chi^{-1}(c):=\\{v\in N\mid\chi(v)=c\\}$ the  _color class of $c$_. For
a subset $N^{\prime}\subseteq N$, we let $\chi(N^{\prime}):=\\{\chi(v)\mid
v\in N^{\prime}\\}$, and for a subset $C\subseteq\\{1,\dots,2k\\}$ we let
$\chi^{-1}(C):=\bigcup_{c\in C}\chi^{-1}(c)$. The following definition is
important for our algorithm.

###### Definition 17

Let $N$ be a set of vertices and let $\chi:N\rightarrow\\{1,\dots,2k\\}$ be a
coloring of $N$. An arc set $A\subseteq N\times N$ is called  _color-loyal for
$\chi$_ if for every color class $\chi^{-1}(c)$ it holds that

  1. a)

there is no $(v,w)\in A$ with $v,w\in\chi^{-1}(c)$, and

  2. b)

there is at most one vertex $v\in\chi^{-1}(c)$ such that
$P_{v}^{A}\neq\emptyset$.

Consider the following auxiliary problem.

Colored BA-BNSL
Input: A set of vertices $N$, local scores $\mathcal{F}=\\{f_{v}\mid v\in
N\\}$, two integers $t,k\in\mathds{N}$, and a coloring
$\chi:N\rightarrow\\{1,\dots,2k\\}$.

Question: Is there an $(N,\mathcal{F},t)$-valid arc set $A\subseteq N\times N$
that is color-loyal for $\chi$ and $|A|\leq k$?

Intuitively, Colored BA-BNSL is the problem that we solve after we randomly
choose a coloring of $N$. The correspondence between BA-BNSL and Colored BA-
BNSL is as follows.

###### Proposition 18

Let $I=(N,\mathcal{F},t,k)$ be an instance of BA-BNSL. If $I$ is a yes-
instance of BA-BNSL, then there exist at least $(2k)!(2k)^{(n-2k)}$ colorings
$\chi:N\rightarrow\\{1,2,\dots,2k\\}$ such that $(N,\mathcal{F},t,k,\chi)$ is
a yes-instance of Colored BA-BNSL.

###### Proof

Let $I$ be a yes-instance of BA-BNSL. Then, there exists an
$(N,\mathcal{F},t)$-valid arc-set $A$ with $|A|\leq k$. Observe that $|A|\leq
k$ implies that there are at most $2k$ vertices of $N$ that are endpoints of
arcs in $A$.

We define a set $\mathbb{X}$ of colorings of $N$, such that
$\chi\in\mathbb{X}$ if $\chi$ assigns the endpoints of arcs in $A$ to pairwise
distinct colors. Since at most $2k$ vertices are endpoints of arcs in $A$, we
conclude that $|\mathbb{X}|\geq(2k)!(2k)^{(n-2k)}$. Let
$I^{\prime}:=(N,\mathcal{F},t,k,\chi)$ for some arbitrary $\chi\in\mathbb{X}$.
We show that $A$ is a solution for $I^{\prime}$. Note that $A$ is
$(N,\mathcal{F},t)$-valid, so it remains to show that $A$ is color-loyal for
$\chi$.

Since all endpoints of arcs in $A$ have pairwise distinct colors under $\chi$
it follows that no $(v,w)\in A$ connects two vertices of the same color class
$\chi^{-1}(c)$. Moreover, it follows that at most one vertex in each color
class $\chi^{-1}(c)$ has a non-empty parent set. Consequently, $I^{\prime}$ is
a yes-instance of Colored BA-BNSL. $\hfill\Box$ ■

We next show that Colored BA-BNSL parameterized by $k$ is fixed-parameter
tractable.

###### Proposition 19

Colored BA-BNSL can be solved in
$\mathcal{O}(4^{k}k^{2}n^{2}\delta_{\mathcal{F}})$ time.

###### Proof

Let $I=(N,\mathcal{F},t,k,\chi)$ be an instance of Colored BA-BNSL with
$f_{v}(\emptyset)=0$ for every $v\in N$ and let $C:=\\{1,2,\dots,2k\\}$ denote
the set of colors. By Proposition 16, every instance of BA-BNSL can be
transformed into such an instance in
$\mathcal{O}(|\mathcal{F}|)=\mathcal{O}(n^{2}\cdot\delta_{\mathcal{F}})$ time.

We fill a dynamic programming table $T$ with entries of type
$T[C^{\prime},k^{\prime}]$ where $C^{\prime}\subseteq C$ and
$k^{\prime}\in\\{0,1,\dots,k\\}$. Every entry stores the maximum value of
$\sum_{v\in\chi^{-1}(C^{\prime})}f_{v}(P^{A}_{v})$ over all possible DAGs
$D=(N,A)$, where $A\subseteq\chi^{-1}(C^{\prime})\times\chi^{-1}(C^{\prime})$
is color-loyal for $\chi$ and contains at most $k^{\prime}$ arcs. We set
$T[\\{c\\},k^{\prime}]:=\sum_{w\in\chi^{-1}(c)}f_{w}(\emptyset)=0$ for every
$c\in C$ and $k^{\prime}\in\\{0,1,\dots,2k\\}$. The recurrence to compute the
entry for $C^{\prime}\subseteq C$ with $|C^{\prime}|>1$ is

$\displaystyle T[C^{\prime},k^{\prime}]=\max_{c\in
C^{\prime}}\max_{v\in\chi^{-1}(c)}\max_{\begin{subarray}{c}P\in\mathcal{P}_{\mathcal{F}}(v)\\\
|P|\leq k^{\prime}\\\ \chi(P)\subseteq
C^{\prime}\setminus\\{c\\}\end{subarray}}H_{C^{\prime}}^{k^{\prime}}(c,v,P)\text{,}$

where

$\displaystyle H_{C^{\prime}}^{k^{\prime}}(c,v,P)=$ $\displaystyle
T[C^{\prime}\setminus\\{c\\},k^{\prime}-|P|]$
$\displaystyle+f_{v}(P)+\sum_{w\in\chi^{-1}(c)\setminus\\{v\\}}f_{w}(\emptyset)\text{.}$

The result can be computed by checking if $T[C,k]\geq t$. Note that the
corresponding network can be found via traceback. The correctness proof is
straightforward and thus omitted. We next consider the running time. The size
of $T$ is $\mathcal{O}(2^{2k}\cdot k)$. Note that
$\sum_{w\in\chi^{-1}(c)\setminus\\{v\\}}f_{w}(\emptyset)=0$ since we applied
the preprocessing from Proposition 16. Therefore, each entry can be computed
in $\mathcal{O}(2k\cdot n^{2}\cdot\delta_{\mathcal{F}})$ time by iterating
over all $2k$ possible colors $c$, all $\mathcal{O}(n)$ vertices $v$ in the
corresponding color class, and all $\mathcal{O}(\delta_{\mathcal{F}}n)$
vertices in possible parent sets of $v$. Altogether, Colored BA-BNSL can be
solved in $\mathcal{O}(4^{k}k^{2}n^{2}\delta_{\mathcal{F}})$ time.
$\hfill\Box$ ■

Propositions 18 and 19 give the following.

###### Theorem 20

There exists a randomized algorithm for BA-BNSL that, in time
$\mathcal{O}((2e)^{2k}\cdot k^{2}n^{2}\delta_{\mathcal{F}})$ returns _no_ , if
given a no-instance and returns _yes_ with a constant probability of at least
$1-\frac{1}{e}$, if given a yes-instance.

###### Proof

We describe the steps of the randomized algorithm applied on an instance
$I=(N,\mathcal{F},t,k)$.

  1. 1.

Color every vertex of $N$ independently with one color from the set
$\\{1,\dots,2k\\}$ with uniform probability. Let
$\chi:N\rightarrow\\{1,\dots,2k\\}$ be the resulting coloring.

  2. 2.

Apply the algorithm from Proposition 19 on the instance
$(N,\mathcal{F},t,k,\chi)$ of Colored BA-BNSL.

  3. 3.

If the answer _yes_ was returned in Step 2, then return _yes_. Otherwise,
return  _no_.

By Proposition 19, one application of the algorithm described above can be
performed in $\mathcal{O}(2^{2k}\cdot k^{2}n^{2}\delta_{\mathcal{F}})$ time.

Given a no-instance, there exists no $(N,\mathcal{F},t)$-valid arc set $A$
with $|A|\leq k$ and therefore the answer _no_ is returned in Step 2.
Conversely, given a yes-instance $I$, we conclude from Proposition 18 that
there exist at least $(2k)!(2k)^{(n-2k)}$ colorings $\chi$ such that
$(N,\mathcal{F},t,k,\chi)$ is a yes-instance of Colored BA-BNSL. The
probability of randomly choosing such coloring $\chi$ is at least

$\displaystyle\frac{(2k)!(2k)^{(n-2k)}}{(2k)^{n}}\geq e^{-2k}.$

Hence, by repeating the algorithm independently $e^{2k}$ times, we obtain a
runningtime bound of $\mathcal{O}((2e)^{2k}\cdot
k^{2}n^{2}\delta_{\mathcal{F}})$ and the algorithm returns _yes_ with a
constant probability of $1-\frac{1}{e}$. $\hfill\Box$ ■

The randomized algorithm from Theorem 20 can be derandomized with standard
techniques Naor et al. (1995); Cygan et al. (2015).

###### Corollary 21

BA-BNSL can be solved in $(2e)^{2k}\cdot
k^{\mathcal{O}(\log(k))}\cdot\text{{poly}}(|I|)$ time.

Bounding the number of arcs appears to be not so relevant for practical use.
However, the algorithm might be useful as a heuristic upper-bound: If we want
do add a restricted number of dependencies to a given Bayesian network, the
result of BA-BNSL gives an upper bound for the profit we can expect from that
modification. The above algorithm is complemented by the following negative
result.

###### Theorem 22

BA-BNSL parameterized by $t+k$ does not admit a polynomial kernel unless
$\text{\rm NP}\subseteq\text{\rm coNP}/\text{\rm poly}$ even whenrestricted to
instances with $k=n^{2}$.

###### Proof

We prove the theorem by giving a polynomial parameter transformation from the
following problem.

Multicolored Independent Set
Input: A properly $\ell$-colored undirected graph $G=(V,E)$ with color classes
$C_{1},\ldots,C_{\ell}\subseteq V$.

Question: Is there an independent set containing one vertex from each color in
$G$?

Multicolored Independent Set does not admit a polynomial kernel when
parameterized by $|C_{1}\cup\dots\cup C_{\ell-1}|$ unless $\text{\rm
NP}\subseteq\text{\rm coNP}/\text{\rm poly}$ Grüttemeier and Komusiewicz
(2020)color=yellow!90!red] We actually proved it for Multicolored Clique.

Construction. Let $G=(V,E)$ be an instance of Multicolored Independent Set
with color classes $C_{1},\dots,C_{\ell}$. We describe how to construct an
equivalent instance $(N,\mathcal{F},t,k)$ of BA-BNSL. First, set $N:=C_{1}\cup
C_{2}\cup\dots\cup C_{\ell-1}\cup\\{x\\}$ for some $x\not\in V$. Second, we
define the local scores $\mathcal{F}$ as follows: Let
$i\in\\{1,\dots,\ell-1\\}$. For $v\in C_{i}$ we set $f_{v}(P)=1$ if
$P=(C_{i}\setminus\\{v\\})\cup(N_{G}(v)\setminus C_{\ell})\cup\\{x\\}$.
Otherwise, we set $f_{v}(P)=0$. For $x$, we set $f_{x}(P)=1$ if there exists
some $w\in C_{\ell}$ with $N_{G}(w)=P$. Otherwise we set $f_{x}(P)=0$.
Finally, we set $t:=\ell$ and $k:=|N|^{2}$.

Observe that the value of the local scores is either $1$ or $0$, and that
there are exactly $|V|$ values where $f_{v}(P)=1$. Hence,
$|\mathcal{F}|\in\mathcal{O}(|V|)$. We can obviously compute
$(N,\mathcal{F},t,k)$ in polynomial time from $G$. Furthermore, recall that
$|N|=|C_{1}\cup\dots\cup C_{\ell-1}|+1$ and therefore, $t+k$ is polynomially
bounded in $|C_{1}\cup\dots\cup C_{\ell}|$.

Intuition: Before we show the correctness of the polynomial parameter
transformation, we start with some intuition. To reach the score $t=\ell$,
exactly one vertex per color class $C_{1},\dots,C_{\ell-1}$ and the vertex $x$
must learn a parent set with score $1$. The vertices from
$C_{1},\dots,C_{\ell-1}$ and the choice of the parent set of $x$ then
correspond to a multicolored set in $G$. The condition that the resulting
directed graph must be a DAG guarantees that the chosen vertices form an
independent set.

Correctness. $(\Rightarrow)$ Let $S=\\{v_{1},\dots,v_{\ell}\\}$ be a
multicolored independent set in $G$ with $v_{i}\in C_{i}$ for all
$i\in\\{1,\dots,\ell\\}$. We define the arc set $A$ by defining the parent
sets of all vertices in $N$: For all $v\in
N\setminus\\{v_{1},\dots,v_{\ell-1}\\}$ we set $P^{A}_{v}:=\emptyset$. Next,
for $v_{i}\in\\{v_{1},\dots,v_{\ell-1}\\}$ we set
$P_{v_{i}}^{A}:=(C_{i}\setminus\\{v_{i}\\})\cup(N_{G}(v_{i})\setminus
C_{\ell})\cup\\{x\\}$. Finally, we set $P^{A}_{x}=N_{G}(v_{\ell})$. Observe
that $|A|<|N|^{2}=k$. We now prove that $A$ is $(N,\mathcal{F},t)$-valid. By
definition of $\mathcal{F}$ it holds that $f_{v}(P^{A}_{v})=1$ for every
$v\in\\{v_{1},\dots,v_{\ell-1},x\\}$. Hence, $\sum_{c\in
N}f_{v}(P^{A}_{v})=\ell=t$.

It remains to show that $D:=(N,A)$ is a DAG. If $D$ contains a directed cycle,
all vertices on the directed cycle have incoming and outgoing arcs. Observe
that $v_{1},\dots,v_{\ell-1}$, and $x$ are the only vertices with incoming
arcs.

We first prove that every $v\in\\{v_{1},\dots,v_{\ell-1}\\}$ is a sink in $D$.
Assume towards a contradiction that there is some
$v\in\\{v_{1},\dots,v_{\ell-1}\\}$ that has an outgoing arc $(v,w)\in A$.
Without loss of generality, let $v=v_{1}$. Since $v_{1}\not\in P^{A}_{v_{1}}$
and only the vertices $v_{1},v_{2},\dots,v_{\ell-1},x$ have parents under $A$,
we conclude $w\in\\{v_{2},\dots,v_{\ell-1},x\\}$. If
$w\in\\{v_{2},\dots,v_{\ell-1}\\}$, then $v\in P^{A}_{w}$ and therefore $v\in
N_{G}(w)$. Otherwise, if $w=x$, then $v\in P^{A}_{x}$ and therefore $v\in
N_{G}(v_{\ell})$. Both cases contradict the fact that $S$ is an independent
set in $G$ and therefore every $v\in\\{v_{1},\dots,v_{\ell-1}\\}$ is a sink in
$D$.

We conclude that $x$ is the only vertex that might have incoming and outgoing
arcs in $D$. Hence, $x$ is the only vertex that might be part of a directed
cycle. Since $x\not\in P^{A}_{x}$ we conclude that there is no cycle in $D$
and therefore $D$ is a DAG.

$(\Leftarrow)$ Let $A$ be an $(N,\mathcal{F},t)$-valid arc set with $|A|\leq
k$. We show that there exists a multicolored independent set $S$ in $G$. To
this end, consider the following claim.

###### Claim 4

  1. a)

There are at least $\ell$ vertices $v\in N$ with $f_{v}(P^{A}_{v})=1$.

  2. b)

For every $C_{i}$ with $i\in\\{1,\dots,\ell-1\\}$ there is at most one vertex
$v_{i}\in C_{i}$ with $f_{v_{i}}(P_{v_{i}}^{A})=1$.

###### Proof

We first show statement $a)$. Since $A$ is $(N,\mathcal{F},t)$-valid we know
that $\sum_{v\in V}f_{v}(P^{A}_{v})\geq t=\ell$. Since every local score is
either $0$ or $1$, statement $a)$ follows.

We next show statement $b)$. Note that $(N,A)$ is a DAG since $A$ is
$(N,\mathcal{F},t)$-valid. Let $i\in\\{1,\dots,\ell-1\\}$. Assume towards a
contradiction that there are distinct $u,v\in C_{i}$ with
$f_{u}(P_{u}^{A})=f_{v}(P_{v}^{A})=1$. Then, by the construction of
$\mathcal{F}$ we conclude $C_{i}\setminus\\{u\\}\subseteq P_{u}^{A}$ and
$C_{i}\setminus\\{v\\}\subseteq P_{v}^{A}$. Hence $(u,v),(v,u)\in A$ which
contradicts the fact that $(N,A)$ is a DAG. Consequently, statement $b)$
holds. $\hfill\Diamond$ ■

From Claim 4 $a)$ and $b)$ we conclude that for each $C_{i}$ with
$i\in\\{1,\dots,\ell-1\\}$ there is exactly one $v_{i}\in C_{i}$ with
$f_{v_{i}}(P^{A}_{v_{i}})=1$ and that $f_{x}(P^{A}_{x})=1$. Moreover,
$f_{x}(P^{A}_{x})=1$ implies that there exists a vertex $v_{\ell}\in C_{\ell}$
with $N_{G}(v_{\ell})=P^{A}_{x}$. We define
$S:=\\{v_{1},\dots,v_{\ell-1},v_{\ell}\\}$ and show that $S$ is a multicolored
independent set in $G$.

Obviously, the vertices of $S$ are from pairwise distinct color classes. Thus,
it remains to show that no two vertices in $S$ are adjacent in $G$. Assume
towards a contradiction that there exist $v,w\in S$ such that $\\{v,w\\}\in
E$. Without loss of generality, let $v=v_{1}$. Consider the following cases.

Case 1: $w\in\\{v_{2},\dots,v_{\ell-1}\\}$. Then, $\\{v,w\\}\in E$ implies
$w\in N_{G}(v)\setminus C_{\ell}$ and $v\in N_{G}(w)\setminus C_{\ell}$.
Together with the fact that $f_{v}(P^{A}_{v})=f_{w}(P^{A}_{w})=1$ we conclude
$(v,w),(w,v)\in A$ which contradicts the fact that $(N,A)$ is a DAG.

Case 2: $w=v_{\ell}$. Then, $\\{v,w\\}\in E$ implies $v\in N_{G}(w)$ and
therefore $v\in P^{A}_{x}$. Moreover $f_{v}(P^{A}_{v})=1$ implies $x\in
P_{v}^{A}$. Hence, $(v,w),(w,v)\in A$ contradicting the fact that $(N,A)$ is a
DAG.

We conclude that no two vertices of $S$ are adjacent in $G$ and therefore, $S$
is a multicolored independent set in $G$. $\hfill\Box$. ■

Observe that for instances of BA-BNSL with $k=n^{2}$, the budget of arcs can
never be exceeded since a DAG has at most $\binom{n}{2}<n^{2}$ arcs. Hence, on
instances with $k=n^{2}$ we ask for an $(N,\mathcal{F},t)$-valid arc set
without additional sparsity constraints. Thus, BA-BNSL and Vanilla-BNSL are
the same when $k=n^{2}$. Then, Theorem 22 implies the following.

###### Corollary 23

Vanilla-BNSL parameterized by $n$ does not admit a polynomial kernel unless
$\text{\rm NP}\subseteq\text{\rm coNP}/\text{\rm poly}$.

##  5 Conclusion

We have outlined the tractability borderline of Bayesian Network Structure
Learning with respect to several structural constraints on the learned network
or on its moralized graph. In particular, we have shown that putting
structural sparsity constraints on the moralized graph may make the problem
harder than putting similar constraints on the network. This is somewhat
counterintuitive since the moralized graph is a supergraph of the underlying
undirected graph of the network. It seems interesting to investigate this
issue further, that is, to find structural constraints such that putting these
constraints on the network leads to an easier problem than putting them on the
moralized graph.

While none of our algorithms have direct practical applications, they may be
useful as subroutines in a branch-and-bound scenario when one may aim to
compute upper or lower bounds on the score that can be achieved for example by
adding $k$ arcs to a network that is currently considered in the search. Thus,
it would be interesting to explore variants of Bayesian Network Structure
Learning where the input contains a partial network and the aim is to extend
it. Do the positive results for Bayesian Network Structure Learning also hold
for this more general problem?

## References

  * Alon et al. [1995] Noga Alon, Raphael Yuster, and Uri Zwick.  Color-coding.  J. ACM, 42(4):844–856, 1995.
  * Chickering [1995] David Maxwell Chickering.  Learning Bayesian networks is NP-complete.  In Proceedings of the Fifth International Conference on Artificial Intelligence and Statistics, (AISTATS’95), pages 121–130. Springer, 1995.
  * Chow and Liu [1968] C. K. Chow and C. N. Liu.  Approximating discrete probability distributions with dependence trees.  IEEE Trans. Information Theory, 14(3):462–467, 1968.
  * Cooper [1990] Gregory F. Cooper.  The computational complexity of probabilistic inference using Bayesian belief networks.  Artif. Intell., 42(2-3):393–405, 1990.
  * Cygan et al. [2015] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer, 2015.
  * Darwiche [2009] Adnan Darwiche.  Modeling and Reasoning with Bayesian Networks.  Cambridge University Press, 2009.
  * Downey and Fellows [1995] Rodney G Downey and Michael R Fellows.  Parameterized computational feasibility.  In Feasible mathematics II, pages 219–244. Springer, 1995.
  * Elidan and Gould [2008] Gal Elidan and Stephen Gould.  Learning bounded treewidth Bayesian networks.  In Proceedings of the Twenty-Second Annual Conference on Neural Information Processing Systems, (NIPS’08), pages 417–424. Curran Associates, Inc., 2008.
  * Fellows et al. [2009] Michael R. Fellows, Danny Hermelin, Frances A. Rosamond, and Stéphane Vialette.  On the parameterized complexity of multiple-interval graph problems.  Theor. Comput. Sci., 410(1):53–61, 2009.
  * Garey and Johnson [1979] M. R. Garey and David S. Johnson.  Computers and Intractability: A Guide to the Theory of NP-Completeness.  W. H. Freeman, 1979.
  * Gaspers et al. [2015] Serge Gaspers, Mikko Koivisto, Mathieu Liedloff, Sebastian Ordyniak, and Stefan Szeider.  On finding optimal polytrees.  Theor. Comput. Sci., 592:49–58, 2015.
  * Grüttemeier and Komusiewicz [2020] Niels Grüttemeier and Christian Komusiewicz.  On the relation of strong triadic closure and cluster deletion.  Algorithmica, 82(4):853–880, 2020.
  * Korhonen and Parviainen [2013] Janne H. Korhonen and Pekka Parviainen.  Exact learning of bounded tree-width Bayesian networks.  In Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, (AISTATS’13), pages 370–378. JMLR.org, 2013.
  * Korhonen and Parviainen [2015] Janne H. Korhonen and Pekka Parviainen.  Tractable Bayesian network structure learning with bounded vertex cover number.  In Proceedings of the Twenty-Eighth Annual Conference on Neural Information Processing Systems, (NIPS’15), pages 622–630. MIT Press, 2015.
  * Meek [2001] Christopher Meek.  Finding a path is harder than finding a tree.  J. Artif. Intell. Res., 15:383–389, 2001.
  * Micali and Vazirani [1980] Silvio Micali and Vijay V. Vazirani.  An ${O(\sqrt{|V|}|E|)}$ Algorithm for finding maximum matching in general graphs.  In Proceedings of the Twenty-First Annual Symposium on Foundations of Computer Science, (FOCS’80), pages 17–27. IEEE Computer Society, 1980.
  * Naor et al. [1995] Moni Naor, Leonard J. Schulman, and Aravind Srinivasan.  Splitters and near-optimal derandomization.  In Proceedings of the Thirty-Sixth Annual Symposium on Foundations of Computer Science, (FOCS’95), pages 182–191. IEEE Computer Society, 1995.
  * Ordyniak and Szeider [2013] Sebastian Ordyniak and Stefan Szeider.  Parameterized complexity results for exact Bayesian network structure learning.  J. Artif. Intell. Res., 46:263–302, 2013.
  * Ott and Miyano [2003] Sascha Ott and Satoru Miyano.  Finding optimal gene networks using biological constraints.  Genome Informatics, 14:124–133, 2003.
  * Parviainen and Koivisto [2009] Pekka Parviainen and Mikko Koivisto.  Exact structure discovery in Bayesian networks with less space.  In Proceedings of the Twenty-Fifth Conference in Uncertainty in Artificial Intelligence (UAI’09), pages 436–443. AUAI Press, 2009.
  * Pietrzak [2003] Krzysztof Pietrzak.  On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems.  J. Comput. Syst. Sci., 67(4):757–771, 2003.
  * Silander and Myllymäki [2006] Tomi Silander and Petri Myllymäki.  A simple approach for finding the globally optimal Bayesian network structure.  In Proceedings of the Twenty-Second Conference in Uncertainty in Artificial Intelligence (UAI’06). AUAI Press, 2006.