# On the Parameterized Complexity of Polytree Learning

Niels Grüttemeier  Christian Komusiewicz&Nils Morawietz Philipps-Universität
Marburg, Marburg, Germany
{niegru, komusiewicz<EMAIL_ADDRESS>Supported by the
Deutsche Forschungsgemeinschaft (DFG), project OPERAH, KO 3669/5-1.

###### Abstract

A Bayesian network is a directed acyclic graph that represents statistical
dependencies between variables of a joint probability distribution. A
fundamental task in data science is to learn a Bayesian network from observed
data. Polytree Learning is the problem of learning an optimal Bayesian network
that fulfills the additional property that its underlying undirected graph is
a forest. In this work, we revisit the complexity of Polytree Learning. We
show that Polytree Learning can be solved in $3^{n}\cdot|I|^{\mathcal{O}(1)}$
time where $n$ is the number of variables and $|I|$ is the total instance
size. Moreover, we consider the influence of the number of variables $d$ that
might receive a nonempty parent set in the final DAG on the complexity of
Polytree Learning. We show that Polytree Learning has no
$f(d)\cdot|I|^{\mathcal{O}(1)}$-time algorithm, unlike Bayesian network
learning which can be solved in $2^{d}\cdot|I|^{\mathcal{O}(1)}$ time. We show
that, in contrast, if $d$ and the maximum parent set size are bounded, then we
can obtain efficient algorithms.

##  1 Introduction

Bayesian networks are the most important tool for modelling statistical
dependencies in joint probability distributions. A Bayesian network consists
of a DAG $(N,A)$ over the variable set $N$ and a set of condiditional
probability tables. Given a Bayesian network and the observed values on some
of its variables, one may infer the probability distributions of the remaining
variables under the observations. One of the drawbacks of using Bayesian
networks is that this inference task is NP-hard. Moreover, the task of
constructing a Bayesian network with an optimal network structure is NP-hard
as well, even on very restricted instances Chickering (1995). In this problem,
we are given a local parent score function
$f_{v}:2^{N\setminus\\{v\\}}\to\mathds{N}_{0}$ for each variable $v$ and the
task is to learn a DAG $(N,A)$ such that the sum of the parent scores over all
variables is maximal.

In light of the hardness of handling general Bayesian networks, the learning
and inference problems for Bayesian networks fulfilling some specific
structural constraints have been studied extensively Pearl (1989); Korhonen
and Parviainen (2013, 2015); Grüttemeier and Komusiewicz (2020a); Ramaswamy
and Szeider (2021).

One of the earliest special cases that has received attention are _tree_
networks, also called _branchings_. A tree is a Bayesian network where every
vertex has at most one parent. In other words, every connected component is a
directed in-tree. Learning and inference can be performed in polynomial time
on trees Chow and Liu (1968); Pearl (1989). Trees are, however, very limited
in their modeling power since every variable may depend only on at most one
other variable. To overcome this problem, a generalization of branchings
called polytrees has been proposed. A polytree is a DAG whose underlying
undirected graph is a forest. An advantage of polytrees is that the inference
task can be performed in polynomial time on them Pearl (1989); Guo and Hsu
(2002). Polytree Learning, the problem of learning an optimal polytree
structure from parent scores, however, remains NP-hard Dasgupta (1999). We
study exact algorithms for Polytree Learning.

#### Related Work.

Polytree Learning is NP-hard even if every parent set with strictly positive
score has size at most 2 Dasgupta (1999). Motivated by the contrast between
the NP-hardness of Polytree Learning and the fact that learning a tree has a
polynomial-time algorithm, the problem of optimally learning polytrees that
are close to trees has been considered. More precisely, it has been shown that
the best polytree among those that can be transformed into a tree by at most
$k$ edge deletions can be found in $n^{\mathcal{O}(k)}|I|^{\mathcal{O}(1)}$
time Gaspers et al. (2015); Safaei et al. (2013) where $n$ is the number of
variables and $|I|$ is the overall input size. Thus, the running time of these
algorithms is polynomial for every fixed $k$. As noted by Gaspers et al.
Gaspers et al. (2015), a brute-force algorithm for Polytree Learning would
need to consider $n^{n-2}\cdot 2^{n-1}$ directed trees. Polytrees have been
used, for example, in image-segmentation for microscopy data Fehri et al.
(2019).

#### Our Results.

We obtain an algorithm that solves Polytree Learning in
$3^{n}\cdot|I|^{\mathcal{O}(1)}$ time. This is the first algorithm for
Polytree Learning where the running time is singly-exponential in the number
of variables $n$. Therunning time is a substantial improvement over the brute-
force algorithm mentioned above, thus positively answering a question of
Gaspers et al. Gaspers et al. (2015) on the existence of such algorithms. We
then study whether Polytree Learning is amenable to polynomial-time data
reduction that shrinks the instance $I$ if $|I|$ is much bigger than $n$.
Using tools from parameterized complexity theory, we show that such a data
reduction algorithm is unlikely. More precisely, we show that (under standard
complexity-theoretic assumptions) there is no polynomial-time algorithm that
replaces any $n$-variable instance $I$ by an equivalent one of size
$n^{\mathcal{O}(1)}$. In other words, it seems necessary to keep an
exponential number of parent sets to compute the optimal polytree.

We then consider a parameter that is potentially much smaller than $n$ and
determine whether Polytree Learning can be solved efficiently when this
parameter is small. The parameter $d$, which we call the number of _dependent_
variables, is the number of variables $v$ for which at least one entry of
$f_{v}$ is strictly positive. The parameter essentially counts how many
variables might receive a nonempty parent set in an optimal solution. We show
that Polytree Learning can be solved in polynomial time when $d$ is constant
but that an algorithm with running time $g(d)\cdot|I|^{\mathcal{O}(1)}$ is
unlikely for any computable function $g$. Consequently, in order to obtain
positive results for the parameter $d$, one needs to consider further
restrictions on the structure of the input instance. We make a first step in
this direction and consider the case where all parent sets with a strictly
positive score have size at most $p$. Using this parameterization, we show
that every input instance can be solved in $2^{\omega
dp}\cdot|I|^{\mathcal{O}(1)}$ time where $\omega$ is the matrix multiplication
constant. With the current-best known value for $\omega$ this gives a running
time of $5.18^{dp}\cdot|I|^{\mathcal{O}(1)}.$ We then consider again data
reduction approaches. This time we obtain a positive result: Any instance of
Polytree Learning where $p$ is constant can be reduced in polynomial time to
an equivalent one of size $d^{\mathcal{O}(1)}$. Informally, this means that if
the instance has only few dependent variables, the parent sets with strictly
positive score are small, and there are many nondependent variables, then we
can identify some nondependent variables that are irrelevant for an optimal
polytree representing the input data. We note that this result is tight in the
following sense: Under standard complexity-theoretic assumptions it is
impossible to replace each input instance in polynomial time by an equivalent
one with $(d+p)^{\mathcal{O}(1)}$ variables. Thus, the assumption that $p$ is
a constant is necessary.

##  2 Preliminaries

#### Notation.

An _undirected graph_ is a tuple $(V,E)$, where $V$ is a set of vertices and
$E\subseteq\\{\\{u,v\\}\mid u,v\in V\\}$ is a set of edges. Given a vertex
$v\in V$, we define $N_{G}(v):=\\{u\in V\mid\\{u,v\\}\in E\\}$ as the
_neighborhood of $v$_. A _directed graph_ is a tuple $(N,A)$, where $N$ is a
set of vertices and $A\subseteq N\times N$ is a set of arcs. If $(u,v)\in A$
we call $u$ a _parent of $v$_ and $v$ a _child of $u$_. A vertex that has no
parents is a  _source_ and a vertex that has no children is a  _sink_.Given a
vertex $v$, we let $P^{A}_{v}:=\\{u\mid(u,v)\in A\\}$ denote the  _parent set_
of $v$. The  _skeleton_ of a directed graph $(N,A)$ is the undirected graph
$(N,E)$ where $\\{u,v\\}\in E$ if and only if $(u,v)\in A$ or $(v,u)\in A$. A
directed acyclic graph is a  _polytree_ if its skeleton is a forest, that is,
the skeleton is acyclic Dasgupta (1999). As a shorthand, we write $P\times
v:=P\times\\{v\\}$ for a vertex $v$ and a set $P\subseteq N$.

#### Problem Definition.

Given a vertex set $N$, a family
$\mathcal{F}:=\\{f_{v}:2^{N\setminus\\{v\\}}\rightarrow\mathds{N}_{0}\mid v\in
N\\}$ is a _family of local scores for $N$_. Intuitively, $f_{v}(P)$ is the
score that a vertex $v$ obtains if $P$ is its parent set. Given a directed
graph $D:=(N,A)$ we define $\text{{score}}(A):=\sum_{v\in N}f_{v}(P^{A}_{v})$.
We study the following computational problem.

Polytree Learning

Input: A set of vertices $N$, local scores $\mathcal{F}=\\{f_{v}\mid v\in
N\\}$, and an integer $t\in\mathds{N}_{0}$.

Question: Is there an arc-set $A\subseteq N\times N$ such that $(N,A)$ is a
polytree and $\text{{score}}(A)\geq t$?

Given an instance $I:=(N,\mathcal{F},t)$ of Polytree Learning, an arc-set $A$
is a _solution of $I$_ if $(N,A)$ is a polytree and ${\text{{score}}(A)\geq
t}$. Without loss of generality we may assume that $f_{v}(\emptyset)=0$ for
every $v\in N$ Grüttemeier and Komusiewicz (2020a). Throughout this work, we
let $n:=|N|$.

#### Solution Structure and Input Representation.

We assume that the local scores $\mathcal{F}$ are given in _non-zero
representation_. That is, $f_{v}(P)$ is part of the input if it is different
from 0. For $N=\\{v_{1},\dots,v_{n}\\}$, the local scores $\mathcal{F}$ are
represented by a two-dimensional array $[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 defined as the number of bits
needed to store this two-dimensional array. Given an instance
$I:=(N,\mathcal{F},t)$, we define $|I|:=n+|\mathcal{F}|+\log(t)$.

For a vertex $v$, we call $\mathcal{P}_{\mathcal{F}}(v):=\\{P\subseteq
N\setminus\\{v\\}\mid f_{v}(P)>0\\}\cup\\{\emptyset\\}$ the  _set of potential
parents of $v$_. Given a yes-instance $I:=(N,\mathcal{F},t)$ of Polytree
Learning, there exists a solution $A$ such that
$P^{A}_{v}\in\mathcal{P}_{\mathcal{F}}(v)$ for every $v\in N$: If there is a
vertex with $P^{A}_{v}\not\in\mathcal{P}_{\mathcal{F}}(v)$ we can simply
replace its parent set by $\emptyset$. The running times presentend in this
paper will also be measured in the maximum number of potential parent sets
$\delta_{\mathcal{F}}:=\max_{v\in N}|\mathcal{P}_{\mathcal{F}}(v)|$ Ordyniak
and Szeider (2013).

A tool for designing algorithms for Polytree Learning is the _directed
superstructure_ Ordyniak and Szeider (2013) which is the directed graph
$S_{\mathcal{F}}:=(N,A_{\mathcal{F}})$ with
$A_{\mathcal{F}}:=\\{(u,v)\mid\exists P\in\mathcal{P}_{\mathcal{F}}(v):u\in
P\\}$. In other words, there is an arc $(u,v)\in A_{\mathcal{F}}$ if and only
if $u$ is a potential parent of $v$.

#### Parameterized Complexity.

A problem is in the class XP for a parameter $k$ if it can be solved in
$|I|^{g(k)}$ time for some computable function $g$. In other words, a problem
is in XP if it can be solved within polynomial time for every fixed $k$. A
problem is fixed-parameter tractable (FPT) for a parameter $k$ if it can be
solved in $g(k)\cdot|I|^{\mathcal{O}(1)}$ time for some computable $g$. If a
problem is W[1]-hard for a parameter $k$, then it is assumed to not be fixed-
parameter tractable for $k$. A _problem kernel_ is an algorithm that, given an
instance $I$ with parameter $k$ computes in polynomial time an equivalent
instance $I^{\prime}$ with parameter $k^{\prime}$ such that
$|I^{\prime}|+k^{\prime}\leq h(k)$ for some computable function $h$. If $h$ is
a polynomial, then the problem admits a _polynomial kernel_. Strong
conditional running time bounds can also be obtained by assuming the
_Exponential Time Hypothesis (ETH)_ , a standard conjecture in complexity
theory Impagliazzo et al. (2001). For a detailed introduction into
parameterized complexity we refer to the standard textbook Cygan et al.
(2015).

##  3 Parameterization by the Number of Vertices

In this section we study the complexity of Polytree Learning when
parameterized by $n$, the number of vertices. Note that there are up to
$n\cdot 2^{n-1}$ entries in $\mathcal{F}$ and thus, the total input size of an
instance of Polytree Learning might be exponential in $n$.On the positive
side, we show that the problem can be solved in
$\mathcal{O}(3^{n}\cdot|I|^{\mathcal{O}(1)})$ time.

On the negative side, we complement the result above by proving that Polytree
Learning does not admit a polynomial kernel when parameterized by $n$. In
other words, it is presumably impossible to transform an instance of Polytree
Learning in polynomial time into an equivalent instance of size
$|I|=n^{\mathcal{O}(1)}$. This shows that it is sometimes necessary to keep an
exponential number of parent scores to compute an optimal polytree.

###  3.1 An FPT Algorithm

######  Theorem 3.1.

Polytree Learning can be solved in $3^{n}\cdot|I|^{\mathcal{O}(1)}$ time.

###### Proof.

Let $I:=(N,\mathcal{F},t)$ be an instance of Polytree Learning. We describe a
dynamic programming algorithm to solve $I$. We suppose an arbitrary fixed
total ordering on the vertices of $N$. For every $P\subseteq N$, and every
$i\in[1,|P|]$, we denote with $p_{i}$ the $i$th smallest element of $P$
according to the total ordering.

The dynamic programming table $T$ has entries of type $T[v,P,S,i]$ with $v\in
N$, $P\in\mathcal{P}_{\mathcal{F}}(v)$, $S\subseteq N\setminus(P\cup\\{v\\})$,
and $i\in[0,|P|]$.

Each entry stores the maximal score of an arc set $A$ of a polytree on
$\\{v\\}\cup P\cup S$ where $v$ has no children, $v$ learns exactly the parent
set $P$ under $A$, and for each $j\in[i+1,|P|]$, only the arc $(p_{j},v)$ is
incident with $p_{j}$ under $A$. See Figure 1 for an illustration.

$P$$p_{1}$$p_{2}$$p_{3}$$p_{4}$$p_{5}$$v$$S$ Figure 1: Illustration of an
entry $T[v,P,S,i]$ where $i=3$.

We initialize the table $T$ by setting $T[v,P,\emptyset,i]:=f_{v}(P)$ for all
$v\in N$, $P\in\mathcal{P}_{\mathcal{F}}(v)$, and $i\in[0,|P|]$. The
recurrence to compute an entry for $v\in N$,
$P\in\mathcal{P}_{\mathcal{F}}(v)$, $S\subseteq N\setminus(P\cup\\{v\\})$, and
$i\in[1,|P|]$ is

$\displaystyle\begin{split}&T[v,P,S,i]:=\max_{S^{\prime}\subseteq
S}T[v,P,S\setminus S^{\prime},i-1]+\\\ &\leavevmode\nobreak\
\leavevmode\nobreak\ \max_{v^{\prime}\in
S^{\prime}\cup\\{p_{i}\\}}\max_{\begin{subarray}{c}P^{\prime}\in\mathcal{P}_{\mathcal{F}}(v^{\prime})\\\
P^{\prime}\subseteq
S^{\prime}\cup\\{p_{i}\\}\end{subarray}}T[v^{\prime},P^{\prime},(S^{\prime}\cup\\{p_{i}\\})\setminus(P^{\prime}\cup\\{v^{\prime}\\}),|P^{\prime}|].\end{split}$

Note that the two vertex sets $P\cup(S\setminus S^{\prime})\cup\\{v\\}$ and
$P^{\prime}\cup(S^{\prime}\cup\\{p_{i}\\})\setminus(P^{\prime}\cup\\{v^{\prime}\\})\cup\\{v^{\prime}\\}=S^{\prime}\cup\\{p_{i}\\}$
share only the vertex $p_{i}$. Hence, combining the polytree on these two
vertex sets results in a polytree.

If $i$ is equal to zero, then the recurrence is

$\displaystyle\begin{split}&T[v,P,S,0]:=\\\ &\leavevmode\nobreak\
\leavevmode\nobreak\ f_{v}(P)+\max_{v^{\prime}\in
S}\max_{\begin{subarray}{c}P^{\prime}\in\mathcal{P}_{\mathcal{F}}(v^{\prime})\\\
P^{\prime}\subseteq
S\end{subarray}}T[v^{\prime},P^{\prime},S^{\prime}\setminus(P^{\prime}\cup\\{v^{\prime}\\}),|P^{\prime}|].\end{split}$

Thus, to determine if $I$ is a yes-instance of Polytree Learning, it remains
to check if $T[v,P,N\setminus(P\cup\\{v\\}),|P|]\geq t$ for some $v\in N$ and
some $P\in\mathcal{P}_{\mathcal{F}}(v)$. The corresponding polytree can be
found via traceback. The correctness proof is straightforward and thus
omitted.

The dynamic programming table $T$ has $2^{n}\cdot
n^{2}\cdot\delta_{\mathcal{F}}$ entries. Each of these entries can be computed
in $2^{|S|}\cdot n^{2}\cdot\delta_{\mathcal{F}}$. Consequently, all entries
can be computed in
$\sum_{i=0}^{n}\binom{n}{i}2^{i}\cdot|I|^{\mathcal{O}(1)}=3^{n}\cdot|I|^{\mathcal{O}(1)}$
time in total. To evaluate if there is some $v\in N$ and some
$P\in\mathcal{P}_{\mathcal{F}}(v)$ such that
$T[v,P,N\setminus(P\cup\\{v\\}),|P|]\geq t$ can afterwards be done in
$\mathcal{O}(n\cdot\delta_{\mathcal{F}})$ time. Hence, the total running time
is $3^{n}\cdot|I|^{\mathcal{O}(1)}$. ∎

#### A Kernel Lower Bound

In this subsection we prove the following kernel lower bound. The proof is
closely related to a similar kernel lower bound for Bayesian Network Structure
Learning parameterized by $n$ Grüttemeier and Komusiewicz (2020a).

######  Theorem 3.2.

Polytree Learning does not admit a polynomial kernel when parameterized by
$n$, unless $\mathrm{NP}\subseteq\mathrm{coNP}/\text{{poly}}$.

###### Proof.

We give a polynomial parameter transformation Bodlaender et al. (2011) from
Multicolored Independent Set.

Multicolored Independent Set
Input: An integer $k$, a graph $G=(V,E)$, and a partition
$(V_{1},\dots,V_{k})$ of $V$ such that $G[V_{i}]$ is a clique for each
$i\in[1,k]$.

Question: Does $G$ contain an independent set of size $k$?

The parameter for this polynomial parameter transformation is the number of
vertices not contained in $V_{k}$.

Given an instance $I=(G=(V,E),k)$ of Multicolored Independent Set with
partition $(V_{1},\dots,V_{k})$ with $\ell:=|V|-|V_{k}|$, we construct in
polynomial time an equivalent instance $I^{\prime}=(N,\mathcal{F},t)$ of
Polytree Learning such that $|N|\in\mathcal{O}(\ell^{2})$ as follows. Let
$V^{<k}:=V\setminus V_{k}$ and let $E^{<k}:=\\{e\in E\mid e\cap
V_{k}=\emptyset\\}$. We set $N:=V^{<k}\cup\\{w_{e}\mid e\in
E^{<k}\\}\cup\\{v^{*}\\}$. For each $v\in V^{<k}$, we set
$P_{v}:=\\{v^{*}\\}\cup\\{w_{\\{v,u\\}}\mid u\in N_{G}(v)\cap V^{<k}\\}$ and
$f_{v}(P_{v}):=1$. Moreover, for each $v\in V_{k}$, we set
$f_{v^{*}}(N_{G}(v)\cap V^{<k}):=1$. All other local scores are set to zero.
Finally, we set $t:=k$. An example of the construction is shown in Figure 2.
We show that $I$ is a yes-instance of Multicolored Independent Set if and only
if $I^{\prime}$ is a yes-instance of Polytree Learning.

$V_{1}$$v_{1}$$V_{2}$$v_{2}$$V_{3}$$v_{3}$$v^{*}$ Figure 2: An example of the
construction given in the proof of Theorem 3.2. The original instance contains
a multicolored independent set on the vertices $v_{1}\in V_{1}$, $v_{2}\in
V_{2}$, $v_{3}\in V_{3}$, and $v_{4}\in V_{4}$. The directed edges represent
the arcs of a polytree with score $4$. The choice of vertex $v_{4}\in V_{4}$
is encoded in the parent set of $v^{*}$.

$(\Rightarrow)$ Let $S$ be an independent set of size $k$ in $G$. Hence, for
each $i\in[1,k]$, there is exactly one $v_{i}\in S\cap V_{i}$, since
$G[V_{i}]$ is is a clique. We set
$P_{i}:=\\{v^{*}\\}\cup\\{e_{\\{v_{i},u\\}}\mid u\in N_{G}(v_{i})\cap
V^{<k}\\}=P_{v_{i}}$ for each $i\in[1,k-1]$ and $P_{k}:=N_{G}(v_{k})\cap
V^{<k}$. By construction, $f_{v_{i}}(P_{i})=1$ for each $i\in[1,k]$ and, thus,
$D:=(N,A)$ with $A:=\cup_{i=1}^{k-1}P_{i}\times v_{i}\cup P_{k}\times v^{*}$
has score $t=k$. Hence, it remains to show that $D$ is a polytree. To this
end, note that $v_{i}\notin N_{G}(v_{k})$ for any $i\in[1,k-1]$ and, thus,
$v_{i}\notin P_{k}$. Consequently, $P_{k}$ is disjoint to all the sets
$\\{v_{i}\\}\cup P_{i}$. Next, we show that $(\\{v_{i}\\}\cup
P_{i})\cap(\\{v_{j}\\}\cup P_{j})=\\{v^{*}\\}$ for distinct $i,j\in[1,k-1],$
which implies that the skeleton of $D$ is acyclic. Since $S$ is an independent
set, there is no edge $e=\\{v_{i},v_{j}\\}\in E^{<k}$ for distinct
$i,j\in[1,k-1]$. Thus, there is no $w_{e}\in P_{i}\cap P_{j}$. Hence,
$(\\{v_{i}\\}\cup P_{i})\cap(\\{v_{j}\\}\cup P_{j})=\\{v^{*}\\}$ and, thus,
$D$ is a polytree. Consequently, $I^{\prime}$ is a yes-instance of Polytree
Learning.

$(\Leftarrow)$ Let $A\subseteq N\times N$ be an arc set such that $D:=(N,A)$
is a polytree with score at least $t=k$, such that each vertex $v\in N$ learns
a potential parent set $P^{A}_{v}\in P_{\mathcal{F}}(v)$ under $A$. By
construction and since $D$ has score at least $t$, there is a set $S^{\prime}$
of at least $k-1$ vertices of $V^{<k}$, such that $v$ learns a parent set of
score one under $A$. Since $G[V_{i}]$ is a clique, $S^{\prime}$ contains
exactly one vertex $v_{i}\in V_{i}$ for each $i\in[1,k-1]$ as, otherwise, the
skeleton of $D$ contains the cycle
$(v^{*},v_{i},w_{\\{v_{i},v_{i}^{\prime}\\}},v_{i}^{\prime})$ for a vertex
$v_{i}^{\prime}\in S^{\prime}\cap V_{i}$. Moreover, there is some $v_{k}\in
V_{k}$ such that $v^{*}$ learns the parent set $P_{k}:=N_{G}(v_{k})\cap
V^{<k}$ under $A$. We set $S:=S^{\prime}\cup\\{v_{k}\\}$ and show that $S$ is
an independent set in $G$.

Let $P_{i}:=\\{v^{*}\\}\cup\\{w_{\\{v_{i},u\\}}\mid u\in N_{G}(v_{i})\cap
V^{<k}\\}$ be the parent set of $v_{i}$ under $A$ for each $i\in[1,k-1]$.
Since $D$ is a polytree and $v^{*}\in P_{i}$ for each $i\in[1,k-1]$, it
follows that $S^{\prime}\cap P_{k}=S^{\prime}\cap N_{G}(v_{k})=\emptyset$ as,
otherwise, $(v^{*},v^{\prime})$ is a cycle in the skeleton of $D$ for any
$v^{\prime}\in N_{G}(v_{k})\cap S^{\prime}$. Moreover, there is no edge
$\\{v_{i},v_{j}\\}\in E$ for distinct $i,j\in[1,k-1]$ as, otherwise,
$(v_{i},w_{\\{v_{i},v_{j}\\}},v_{j},x)$ is a cycle in the skeleton of $D$.
Consequently, $S$ is an independent set of size $k$ in $G$ and, thus, $I$ is a
yes-instance of Multicolored Independent Set.

Unless $\mathrm{NP}\subseteq\mathrm{coNP}/\text{{poly}}$, Multicolored
Independent Set does not admit a polynomial kernel when parameterized by
$\ell$ Grüttemeier and Komusiewicz (2020b). Since
$|N|\leq\binom{\ell}{2}+\ell+2$ it follows that Polytree Learning does not
admit a polynomial kernel when parameterized by $|N|$, unless
$\mathrm{NP}\subseteq\mathrm{coNP}/\text{{poly}}$. ∎

##  4 Dependent Vertices

We now introduce a new parameter $d$ called  _number of dependent vertices_.
Given an instance $(N,\mathcal{F},t)$ of Polytree Learning, a vertex $v\in N$
is called _dependent_ if there is a nonempty potential parent-set
$P\in\mathcal{P}_{\mathcal{F}}(v)$. Thus, a vertex is dependent if it might
learn a nonempty parent set in a solution. A vertex that is not dependent is
called  _nondependent vertex_. Observe that $d$ is potentially smaller than
$n$. We start with a simple XP-result.

######  Theorem 4.1.

Polytree Learning can be solved in ${(\delta_{\mathcal{F}})}^{d}\cdot
n^{\mathcal{O}(1)}$ time.

###### Proof.

Choose for each dependent vertex $v_{i}$ one of its potential parent sets
$P_{i}\in\mathcal{P}_{\mathcal{F}}(v_{i})$ and check afterwards if
$(N,\cup_{i=1}^{d}P_{i}\times v_{i})$ is a polytree of score at least $t$.
This is the case for some combination of potential parent sets if and only if
the instance is a yes-instance. Since each check can be done in polynomial
time and there are ${(\delta_{\mathcal{F}})}^{d}$ many combinations of
potential parent sets, we obtain the stated running time. ∎

We next show that there is little hope for a significant running time
improvement on this simple brute-force algorithm. More precisely, we show that
there is no $g(d)\cdot|I|^{\mathcal{O}(1)}$-time algorithm for some computable
function $g$ (unless $\text{FPT}=\text{W[1]}$) and a stronger ETH-based
running time bound.

######  Theorem 4.2.

Polytree Learning is W[1]-hard when parameterized by the number of dependent
vertices $d$; if the ETH holds, then it has no
${(\delta_{\mathcal{F}})}^{o(d)}\cdot|I|^{\mathcal{O}(1)}$-time algorithm.
Both results even hold for instances where the directed superstructure
$S_{\mathcal{F}}$ is a DAG.

###### Proof.

We reduce from Independent Set where one is given an undirected graph
$G=(V,E)$ and an integer $k$ and the question is whether there is a subset
$S\subseteq V$ of size at least $k$ such that no two vertices in $S$ are
connected by an edge. Independent Set is $\mathrm{W}[1]$-hard when
parameterized by $k$ Downey and Fellows (2013).

Given an instance $I=(G=(V,E),k)$ of Independent Set, we describe how to
construct an equivalent instance $I^{\prime}=(N,\mathcal{F},t)$ of Polytree
Learning in polynomial time such that at most $k$ vertices have a nonempty
potential parent set. Note that we can assume that every vertex of $G$ has
degree at least one. We start with an empty set $N$ and add $k+1$ vertices
$v_{1},\dots,v_{k},$ and $v^{*}$. Moreover, we add a vertex $w_{e}$ for each
edge $e\in E$. For every vertex $v\in V$, we set $P_{v}:=\\{w_{\\{v,u\\}}\mid
u\in N_{G}(v)\\}\cup\\{v^{*}\\}$ and we set $f_{v_{i}}(P_{v}):=1$ for each
$i\in[1,k]$. All other local scores are set to 0. Finally, we set $t:=k$. This
completes the construction of $I^{\prime}$. Next, we show that $I$ is a yes-
instance of Independent Set if and only if $I^{\prime}$ is a yes-instance of
Polytree Learning.

$(\Rightarrow)$ Let $S\subseteq V$ be an independent set of size $k$ in $G$.
Moreover, let $S=\\{u_{1},\dots,u_{k}\\}$. We set
$A:=\cup_{i=1}^{k}P_{u_{i}}\times v_{i}$ and show that $D=(N,A)$ is a polytree
of score $t=k$. Since $S$ is an independent set in $G$, for every edge $e\in
E$, $w_{e}$ is the endpoint of at most one arc in $A$. Moreover, there is no
arc $(v_{i},v_{j})$ contained in $A$ and $v^{*}$ is only an endpoint of the
arcs $(v^{*},v_{i})$ for each $i\in[1,k]$. As a consequence, $D$ is a polytree
and has score $k$ due to the fact that $f_{v_{i}}(P_{u_{i}})=1$ for all
$i\in[1,k]$. Hence, $I^{\prime}$ is a yes-instance of Polytree Learning.

$(\Leftarrow)$ Let $A\subseteq N\times N$ be an arc set such that $D=(N,A)$ is
a polytree with score at least $t=k$. By construction, only the vertices
$v_{1},\dots,v_{k}$ can learn a nonempty potential parent set. Moreover, no
parent set has score larger than one. As a consequence, for every $i\in[1,k]$
there is some $u_{i}\in V$ such that $v_{i}$ learns the parent set $P_{u_{i}}$
under $A$. We show that $S:=\\{u_{1},\dots,u_{k}\\}$ is an independent set of
size $k$ in $G$. By construction of the local scores, each parent set $P_{i}$
contains the vertex $v^{*}$. Since every vertex of $G$ has degree at least
one, each such parent set has size at least two. Hence, the vertices $u_{i}$
and $u_{j}$ are distinct if $i\neq j$ as, otherwise, the skeleton of $D$ would
contain the cycle $(v_{i},v^{*},v_{j},w_{e})$ for each $w_{e}\in
P_{u_{i}}\setminus\\{v^{*}\\}$. Moreover, since $D$ is a polytree, distinct
vertices $u_{i}$ and $u_{j}$ are not adjacent in $G$ as, otherwise, the vertex
$w_{\\{u_{i},u_{j}\\}}$ is contained in both the learned parent sets
$P_{u_{i}}$ and $P_{u_{j}}$ and, hence, the cycle
$(v_{i},v^{*},v_{j},w_{\\{u_{i},u_{j}\\}})$ is contained in the skeleton of
$D$. Consequently, $I$ is a yes-instance of Independent Set since $S$ is an
independent set of size $k$ in $G$.

In the constructed instance, $d=k$ and $\delta_{\mathcal{F}}=n+1$. Unless the
ETH fails, Independent Set cannot be solved in $n^{o(k)}$ time Chen et al.
(2006) and, hence, Polytree Learning cannot be solved in
$(\delta_{\mathcal{F}})^{o(d)}\cdot|I|^{\mathcal{O}(1)}$ time. ∎

Theorem 4.2 points out a difference between Polytree Learning and Bayesian
Network Structure Learning (BNSL), where we aim to learn a DAG. In BNSL, a
nondependent vertex $v$ can be easily removed from the input instance
$(N,\mathcal{F},t)$ by setting $N^{\prime}:=N\setminus\\{v\\}$ and modifying
the local scores to $f^{\prime}_{u}(P):=\max(f_{u}(P),f_{u}(P\cup\\{v\\}))$.

##  5 Dependent Vertices and Small Parent Sets

Due to Theorem 4.2, fixed-parameter tractability for Polytree Learning
parameterized by $d$ is presumably not possible. However, in instances
constructed in the proof of Theorem 4.2 the maximum parent set size $p$ is not
bounded by some computable function in $d$. In practice there are many
instances where $p$ is relatively small or upper-bounded by some small
constant van Beek and Hoffmann (2015). First, we provide an FPT algorithm for
the parameter $d+p$, the sum of the number of dependent vertices and the
maximum parent set size. Second, we provide a polynomial kernel for the
parameter $d$ if the maximum parent set size $p$ is constant. Both results are
based on computing max $q$-representative sets in a matroid Fomin et al.
(2014); Lokshtanov et al. (2018).

To apply the technique of representative sets we assume that there is a
solution with exactly $d\cdot p$ arcs and every nonempty potential parent set
contains exactly $p$ vertices. This can be obtained with the following simple
modification of an input instance $(N,\mathcal{F},t)$: For every dependent
vertex $v$ we add vertices $v_{1},v_{2},\dots,v_{p}$ to $N$ and set
$f_{v_{i}}(P):=0$ for all their local scores. Then, for every potential parent
set $P\in P_{\mathcal{F}}(v)$ with $|P|<p$ we set
$f_{v}(P\cup\\{v_{1},\dots,v_{p-|P|}\\}):=f_{v}(P)$ and, afterwards, we set
$f_{v}(P):=0$. Then, the given instance is a yes-instance if and only if the
modified instance has a solution with exactly $d\cdot p$ arcs. Furthermore,
note that $f_{v}(\emptyset)=0$ for every dependent vertex and every nonempty
potential parent set has size exactly $p$ after applying the modification.
Before we present the results of this section we state the definition of a
matroid.

######  Definition 5.1.

A pair $M=(E,\mathcal{I})$, where $E$ is a set and $\mathcal{I}$ is a family
of subsets of $E$ is a _matroid_ if

  1. 1.

$\emptyset\in\mathcal{I}$,

  2. 2.

if $A\in\mathcal{I}$ and $B\subseteq A$, then $B\in\mathcal{I}$, and

  3. 3.

if $A,B\in\mathcal{I}$ and $|A|<|B|$, then there exists some $b\in B\setminus
A$ such that $A\cup\\{b\\}\in\mathcal{I}$.

Given a matroid $M=(E,\mathcal{I})$, the sets in $\mathcal{I}$ are called
_independent sets_. A _representation of $M$ over a field $\mathds{F}$_ is a
mapping $\varphi:E\rightarrow V$ where $V$ is some vector space over
$\mathds{F}$ such that $A\in\mathcal{I}$ if and only if the vectors
$\varphi(a)$ with $a\in A$ are linearly independent in $V$. A matroid with a
representation is called  _linear matroid_. Given a set $B\subseteq E$, a set
$A\subseteq E$ _fits_ $B$ if $A\cap B=\emptyset$ and $A\cup B\in\mathcal{I}$.

######  Definition 5.2.

Let $M=(E,\mathcal{I})$ be a matroid, let $\mathcal{A}$ be a family of subsets
of $E$, and let $w:\mathcal{A}\rightarrow\mathds{N}_{0}$ be a weight function.
A subfamily $\widehat{\mathcal{A}}\subseteq\mathcal{A}$ _max $q$-represents_
$\mathcal{A}$ (with respect to $w$) if for every set $B\subseteq E$ with
$|B|=q$ the following holds: If there is a set $A\in\mathcal{A}$ that fits
$B$, there exists some $\widehat{A}\in\widehat{\mathcal{A}}$ that fits $B$,
and $w(\widehat{A})\geq w(A)$. If $\widehat{\mathcal{A}}$ max $q$-represents
$\mathcal{A}$ we write $\widehat{\mathcal{A}}\subseteq^{q}\mathcal{A}$.

We refer to a set family $\mathcal{A}$ where every $A\in\mathcal{A}$ has size
exactly $x\in\mathds{N}_{0}$ as an  _$x$ -family_. Our results rely on the
fact that max $q$-representative sets of an $x$-family can be computed
efficiently as stated in a theorem by Lokshtanov et al. Lokshtanov et al.
(2018) that is based on an algorithm by Fomin et al. Fomin et al. (2014). In
the following, $\omega<2.373$ is the matrix multiplication constant Williams
(2012).

######  Theorem 5.3 (Lokshtanov et al. (2018)).

Let $M=(E,\mathcal{I})$ be a linear matroid which representation can be
encoded with a $k\times|E|$ matrix over the field $\mathds{F}_{2}$ for some
$k\in\mathds{N}$. Let $\mathcal{A}$ be an $x$-family containing $\ell$ sets,
and let $w:\mathcal{A}\rightarrow\mathds{N}_{0}$ be a weight function. Then,

  1. a)

there exists some $\widehat{\mathcal{A}}\subseteq^{q}\mathcal{A}$ of size
$\binom{x+q}{x}$ that can be computed with
$\mathcal{O}\left(\binom{x+q}{x}^{2}\cdot\ell
x^{3}k^{2}+\ell\binom{x+q}{q}^{\omega}kx\right)+(k+|E|)^{\mathcal{O}(1)}$
operations in $\mathds{F}_{2}$, and

  2. b)

there exists some ${\widehat{\mathcal{A}}\subseteq^{q}\mathcal{A}}$ of size
${\binom{x+q}{x}\cdot k\cdot x}$ that can be computed with
$\mathcal{O}\Big{(}\binom{x+q}{x}\cdot\ell
x^{3}k^{2}+\ell\binom{x+q}{q}^{\omega-1}(kx)^{\omega-1}\Big{)}+(k+|E|)^{\mathcal{O}(1)}$
operations in $\mathds{F}_{2}$.

We next define the matroid we use in this work. Recall that, given an instance
$(N,\mathcal{F},t)$ of Polytree Learning, the directed superstructure
$S_{\mathcal{F}}$ is defined as $S_{\mathcal{F}}:=(N,A_{\mathcal{F}})$ where
$A_{\mathcal{F}}$ is the set of arcs that are potentially present in a
solution, and we set $m:=|A_{\mathcal{F}}|$. In this work we consider the
_super matroid_ $M_{\mathcal{F}}$ which we define as the graphic matroid Tutte
(1965) of the super structure. Formally,
$M_{\mathcal{F}}:=(A_{\mathcal{F}},\mathcal{I})$ where $A\subseteq
A_{\mathcal{F}}$ is independent if and only $(N,A)$ is a polytree.

The super matroid is closely related to the  _acyclicity matroid_ that has
been used for a constrained version of Polytree Learning Gaspers et al.
(2015). The proof of the following proposition is along the lines of the proof
that the graphic matroid is a linear matroid. We provide it here for sake of
completeness.

######  Proposition 5.4.

Let $(N,\mathcal{F},t)$ be an instance of Polytree Learning. Then, the super
matroid $M_{\mathcal{F}}$ is a linear matroid and its representation can be
encoded by an $n\times m$ matrix over the field $\mathds{F}_{2}$.

###### Proof.

We first show that $M_{\mathcal{F}}$ is a matroid. Since $(N,\emptyset)$
contains no cycles, it holds that $\emptyset\in\mathcal{I}$. Next, if $(N,A)$
is a polytree for some $A\subseteq A_{\mathcal{F}}$, then $(N,B)$ is a
polytree for every $B\subseteq A$. Thus, Conditions $1$ and $2$ from
Definition 5.1 hold.

We next show that Condition $3$ holds. Consider $A,B\in\mathcal{I}$ with
$|A|<|B|$. Let $N^{\prime}\subseteq N$ be the vertices of a connected
component of $(N,A)$. Since $(N,B)$ is a polytree, the number of arcs in $B$
between vertices of $N^{\prime}$ is at most the number of arcs in $A$ between
the vertices of $N^{\prime}$. Then, since $|B|>|A|$, there exists some
$(u,v)\in B\setminus A$ that has endpoints in two distinct connected
components of $(N,A)$. Thus, $(N,A\cup\\{(u,v)\\})$ is a polytree.
Consequently, $M_{\mathcal{F}}$ is a matroid.

We next consider the representation of $M_{\mathcal{F}}$. Let
$v_{1},\dots,v_{n}$ be the elements of $N$. We define the mapping
$\varphi:A_{\mathcal{F}}\rightarrow{\mathds{F}_{2}}^{n}$ by letting
$\varphi((v_{i},v_{j}))$ be the vector where the $i$-th and the $j$-th entry
equal $1$ and all other entries equal $0$. It is easy to see that an arc-set
$A$ is independent in $M_{\mathcal{F}}$ if and only if the $\varphi(a)$ with
$a\in A$ are linearly independent in ${\mathds{F}_{2}}^{n}$. Clearly,
$\varphi$ can be encoded by an $n\times m$ matrix over $\mathds{F}_{2}$. ∎

###  5.1 An FPT Algorithm

We now use the super matroid $M_{\mathcal{F}}$ to show that Polytree Learning
can be solved in $2^{\omega dp}\cdot|I|^{\mathcal{O}(1)}$ time where $\omega$
is the matrix multiplication constant. The idea of the algorithm is simple:
Let $H:=\\{v_{1},\dots,v_{d}\\}$ be the set of dependent vertices, and for
$i\in\\{0,1,\dots,d\\}$ let $H_{i}:=\\{v_{1},\dots,v_{i}\\}$ be the set
containing the first $i$ dependent vertices. The idea is that, for every
$H_{i}$, we compute a family $\mathcal{A}_{i}$ of possible polytrees where
only the vertices from $\\{v_{1},\dots,v_{i}\\}$ learn a nonempty potential
parent set. We use the algorithm behind Theorem 5.3 as a subroutine to delete
arc-sets from $\mathcal{A}_{i}$ that are not necessary to find a solution. We
next define the operation $\oplus$. Intuitively, $\mathcal{A}\oplus_{v}P$
means that we extend each possible solution in the family $\mathcal{A}$ by the
arc-set that defines $P$ as the parent set of a vertex $v$.

######  Definition 5.5.

Let $v\in N$, and let $\mathcal{A}$ be an $x$-family of subsets of
$A_{\mathcal{F}}$ such that $P^{A}_{v}=\emptyset$ for every $A\in\mathcal{A}$.
For a vertex set $P\subseteq N$ we define

$\displaystyle\mathcal{A}\oplus_{v}P:=\\{A\cup(P\times v)\mid
A\in\mathcal{A}\text{ and }A\cup(P\times v)\in\mathcal{I}\\}.$

Observe that for every $A\in\mathcal{A}$, the set $P\times v$ is disjoint from
$A$ since $P^{A}_{v}=\emptyset$. Consequently, $\mathcal{A}\oplus_{v}P$ is an
$(x+|P|)$-family. The next lemma ensures that some operations (including
$\oplus$) are compatible with representative sets.

######  Lemma 5.6.

Let $w:2^{A_{\mathcal{F}}}\rightarrow\mathds{N}_{0}$ be a weight function with
$w(A):=\text{{score}}(A)$. Let $\mathcal{A}$ be an $x$-family of subsets of
$A_{\mathcal{F}}$.

  1. a)

If $\widetilde{\mathcal{A}}\subseteq^{q}\mathcal{A}$ and
$\widehat{\mathcal{A}}\subseteq^{q}\widetilde{\mathcal{A}}$, then
$\widehat{\mathcal{A}}\subseteq^{q}\mathcal{A}$.

  2. b)

If $\widehat{\mathcal{A}}\subseteq^{q}\mathcal{A}$ and $\mathcal{B}$ is an
$x$-family of subsets of $A_{\mathcal{F}}$ with
$\widehat{\mathcal{B}}\subseteq^{q}\mathcal{B}$, then
$\widehat{\mathcal{A}}\cup\widehat{\mathcal{B}}\subseteq^{q}\mathcal{A}\cup\mathcal{B}$.

  3. c)

Let $v\in N$ and let $P\subseteq N$ such that $P^{A}_{v}=\emptyset$ for every
$A\in\mathcal{A}$. Then, if
$\widehat{\mathcal{A}}\subseteq^{q+|P|}\mathcal{A}$ it follows that
$\widehat{\mathcal{A}}\oplus_{v}P\subseteq^{q}\mathcal{A}\oplus_{v}P$.

###### Proof.

Statements $a)$ and $b)$ are well-known facts Cygan et al. (2015); Fomin et
al. (2014). We prove Statement $c)$. Let $B$ be a set of size $q$. Let there
be a set $A\cup(P\times v)\in\mathcal{A}\oplus_{v}P$ that fits $B$. That is,

$\displaystyle B\cap(A\cup(P\times v))=\emptyset,\text{ and}$ (1)
$\displaystyle B\cup(A\cup(P\times v))\in\mathcal{I}.$ (2)

We show that there is some $\widehat{A}\cup(P\times
v)\in\widehat{\mathcal{A}}\oplus_{v}P$ that fits $B$ and
$w(\widehat{A}\cup(P\times v))\geq w(A\cup(P\times v))$. To this end, observe
that Property (1) implies

$\displaystyle B\cap A=\emptyset,\text{ and }$ (3) $\displaystyle
B\cap(P\times v)=\emptyset.$ (4)

We define $\overline{B}:=B\cup(P\times v)$. Observe that Property (3) together
with $A\cap(P\times v)=\emptyset$ implies $\overline{B}\cap A=\emptyset$, and
that Property (2) implies $A\cup\overline{B}\in\mathcal{I}$. Consequently, $A$
fits $\overline{B}$. Then, since $|\overline{B}|=q+|P|$ due to Property (4)
and $\widehat{\mathcal{A}}\subseteq^{q+|P|}\mathcal{A}$, there exists some
$\widehat{A}\in\widehat{\mathcal{A}}$ that fits $\overline{B}$ and
$w(\widehat{A})\geq w(A)$.

Consider $\widehat{A}\cup(P\times v)$. Since $\widehat{A}$ fits $\overline{B}$
it holds that $(\widehat{A}\cup(P\times v))\cup B\in\mathcal{I}$. Moreover,
observe that $w(\widehat{A}\cup(P\times v))=w(\widehat{A})+f_{v}(P)\geq
w(A)+f_{v}(P)=w(A\cup(P\times v))$. It remains to show that
$(\widehat{A}\cup(P\times v))\cap B=\emptyset$. Since $\widehat{A}$ fits
$\overline{B}$ and $B\subseteq\overline{B}$ it holds that $\widehat{A}\cap
B=\emptyset$. Then, Property (4) implies $(\widehat{A}\cup(P\times v))\cap
B=(\widehat{A}\cap B)\cup((P\times v)\cap B))=\emptyset$. Thus,
$\widehat{A}\cup(P\times v)$ fits $B$ and therefore
$\widehat{\mathcal{A}}\oplus_{v}P\subseteq^{q}\mathcal{A}\oplus_{v}P$. ∎

We now describe the FPT algorithm. Let $I:=(N,\mathcal{F},t)$ be an instance
of Polytree Learning. Let $H:=\\{v_{1},v_{2},\dots,v_{d}\\}$ denote the set of
dependent vertices of $I$, and for $i\in\\{0,1,\dots,d\\}$ let
$H_{i}:=\\{v_{1},\dots,v_{i}\\}$ contain the first $i$ dependent vertices.
Observe that $H_{0}=\emptyset$ and $H_{d}=H$. We define $\mathcal{A}_{i}$ as
the family of possible directed graphs (even the graphs that are no polytrees)
where only the vertices in $H_{i}$ learn a nonempty potential parent set.
Formally, this is

$\displaystyle\mathcal{A}_{i}:=\left\\{A\subseteq
A_{\mathcal{F}}\middle|\begin{array}[]{l}P^{A}_{v}\in\mathcal{P}_{\mathcal{F}}(v)\setminus\\{\emptyset\\}\text{
for all }v\in H_{i}\\\ P^{A}_{v}=\emptyset\text{ for all }v\in N\setminus
H_{i}\end{array}\right\\}.$

The algorithm is based on the following recurrence.

######  Lemma 5.7.

If $i=0$, then $\mathcal{A}_{i}=\\{\emptyset\\}$. If $i>0$, $\mathcal{A}_{i}$
can be computed by

$\displaystyle\mathcal{A}_{i}=\bigcup_{P\in\mathcal{P}_{\mathcal{F}}(v_{i})\setminus\\{\emptyset\\}}\mathcal{A}_{i-1}\oplus_{v_{i}}P.$

Input: $(N,\mathcal{F},t)$ and dependent vertices $v_{1},\dots,v_{d}$

1 $\widehat{\mathcal{A}}_{0}:=\\{\emptyset\\}$

2 for  _$i=1\dots d$_ do

3
$\widetilde{\mathcal{A}}_{i}=\bigcup_{P\in\mathcal{P}_{\mathcal{F}}(v_{i})\setminus\\{\emptyset\\}}\widehat{\mathcal{A}}_{i-1}\oplus_{v_{i}}P$

4 $\widehat{\mathcal{A}}_{i}:=$
ComputeRepresentation$(\widetilde{\mathcal{A}}_{i},(d-i)\cdot p)$

5return $\widehat{A}\in\widehat{\mathcal{A}}_{d}$ such that $(N,\widehat{A})$
is a polytree and $\text{{score}}(\widehat{A})$ is maximal

Algorithm 1 FPT-algorithm for parameter $d+p$

Intuitively, Lemma 5.7 states that $\mathcal{A}_{i}$ can be computed by
considering $\mathcal{A}_{i-1}$ and combining every $A\in\mathcal{A}_{i-1}$
with every arc-set that defines a nonempty potential parent set of $v_{i}$.
The correctness proof is straightforward and thus omitted. We next present the
FPT algorithm.

######  Theorem 5.8.

Polytree Learning can be solved in $2^{\omega dp}\cdot|I|^{\mathcal{O}(1)}$
time, where $\omega$ is the matrix multiplication constant.

###### Proof.

Let $I:=(N,\mathcal{F},t)$ be an instance of Polytree Learning with dependent
vertices $H=\\{v_{1},\dots,v_{d}\\}$, let the families $\mathcal{A}_{i}$ for
$i\in\\{0,1,\dots,d\\}$ be defined as above, and let
$w:2^{A_{\mathcal{F}}}\rightarrow\mathds{N}_{0}$ be defined by
$w(A):=\text{{score}}(A)$. All representing families considered in this proof
are max representing families with respect to $w$. We prove that Algorithm 1
computes an arc-set $A$ such that $(N,A)$ is a polytree with maximal score.

The subroutine ComputeRepresentation$(\widetilde{\mathcal{A}}_{i},(d-i)\cdot
p)$ in Algorithm 1 is an application of the algorithm behind Theorem 5.3 $b)$.
It computes a max $((d-i)\cdot p)$-representing family for
$\widetilde{\mathcal{A}}_{i}$. As a technical remark we mention that the
algorithm as described by Lokshtanov et al. Lokshtanov et al. (2018) evaluates
the weight $w(A)$ for $|\widetilde{\mathcal{A}}_{i}|$ many arc-sets $A$. We
assume that each such evaluation $w(A)$ is replaced by the computation of
$\text{{score}}(A)=\sum_{v\in H}f_{v}(P^{A}_{v})$ which can be done in
$|I|^{\mathcal{O}(1)}$ time.

Correctness. We first prove the following invariant.

######  Claim 1.

The family $\widehat{\mathcal{A}}_{i}$ max $((d-i)\cdot p)$-represents
$\mathcal{A}_{i}$ and
$|\widehat{\mathcal{A}}_{i}|\leq\max(1,\binom{dp}{ip}\cdot n\cdot i\cdot p)$.

######  Proof.

The loop-invariant holds before entering the loop since
$\widehat{\mathcal{A}}_{0}:=\\{\emptyset\\}$ in Line 1 and
$\mathcal{A}_{0}=\\{\emptyset\\}$. Suppose that the loop-invariant hold for
the $(i-1)$th execution of the loop. We show that the loop-invariant holds
after the $i$th execution.

First, consider Line 1. Since we assume that every nonempty potential parent
set contains exactly $p$ vertices, Lemma 5.6 and Lemma 5.7 imply that
$\widetilde{\mathcal{A}}_{i}$ max $((d-i)\cdot p)$-represents
$\mathcal{A}_{i}$. Note that at this point $\widetilde{A}_{i}$ contains up to
$\max(1,\binom{dp}{(i-1)p}\cdot n\cdot(i-1)\cdot p)\cdot\delta_{\mathcal{F}}$
sets.

Next, consider Line 1. Since we assume that every nonempty potential parent
set contains exactly $p$ vertices, the family $\widetilde{A}_{i}$ is an
$(i\cdot p)$-family. Then, the algorithm behind Theorem 5.3 computes a
$((d-i)\cdot p)$-representing family $\widehat{\mathcal{A}}_{i}$. Then, by
Theorem 5.3 $b)$ and Lemma 5.6 $a)$, $\widehat{\mathcal{A}}_{i}$ max
$((d-i)\cdot p)$-represents $\mathcal{A}_{i}$ and
$|\widehat{\mathcal{A}}_{i}|\leq\binom{dp}{ip}\cdot n\cdot i\cdot p$ after the
execution of Line 1.$\hfill\Diamond$

We next show that $\widehat{\mathcal{A}}_{d}$ contains an arc-set that defines
a polytree with maximum score and thus, a solution is returned in Line 1.
Since we assume that there is an optimal solution $A$ that consists of exactly
$d\cdot p$ arcs, this solution is an element of the family $\mathcal{A}_{d}$.
Then, since $\widehat{\mathcal{A}}_{d}\subseteq^{0}\mathcal{A}_{d}$, there
exists some $\widehat{A}\in\widehat{\mathcal{A}}_{d}$ with
$\widehat{A}\cup\emptyset\in\mathcal{I}$ and $w(\widehat{A})\geq w(A)$. Since
$\widehat{A}\cup\emptyset\in\mathcal{I}$, the graph $(N,\widehat{A})$ is a
polytree, and since $w(\widehat{A})\geq w(A)$ the score of $\widehat{A}$ is
maximal.

Running time. We next analyze the running time of the algorithm. For this
analysis, we use the inequality $\binom{a}{b}\leq 2^{a}$ for every $b\leq a$.
Let $i$ be fixed.

We first analyze the running time of one execution of Line 1. Since
$\widehat{\mathcal{A}}_{i-1}$ has size at most $\binom{dp}{(i-1)p}\cdot n\cdot
i\cdot p$ due to Claim 1, Line 1 can be executed in
$2^{dp}\cdot|I|^{\mathcal{O}(1)}$ time.

We next analyze the running time of one execution of Line 1. Recall that
$\widetilde{\mathcal{A}}_{i}$ is an $(i\cdot p)$-family of size at most
$\binom{dp}{(i-1)p}\cdot n\cdot i\cdot p\cdot\delta_{\mathcal{F}}$.
Furthermore, recall that there are $|\widetilde{\mathcal{A}}_{i}|$ many
evaluations of the weight function. Combining the running time from Theorem
5.3 $b)$ with the time for evaluating $w$, the subroutine takes time

$\displaystyle\begin{split}&\mathcal{O}\left(\binom{dp}{ip}\binom{dp}{(i-1)p}\delta_{\mathcal{F}}(i\cdot
p)^{4}n^{3}\right.\\\ &\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
+\left.\binom{dp}{(i-1)p}\delta_{\mathcal{F}}\binom{dp}{ip}^{\omega-1}(n\cdot
i\cdot p)^{\omega}\right)\end{split}$ $\displaystyle+(n+m)^{\mathcal{O}(1)}$
$\displaystyle+\underbrace{\binom{dp}{(i-1)p}\cdot n\cdot i\cdot
p\cdot\delta_{\mathcal{F}}\cdot|I|^{\mathcal{O}(1)}}_{\text{evaluating }w}.$

Therefore, one execution of Line 1 can be done in $2^{\omega
dp}|I|^{\mathcal{O}(1)}$ time. Since there are $d$ repetitions of Lines 1–1,
and Line 1 can be executed in $|I|^{\mathcal{O}(1)}$ time, the algorithm runs
within the claimed running time.∎

###  5.2 Problem Kernelization

We now study problem kernelization for Polytree Learning parameterized by $d$
when the maximum parent set size $p$ is constant. We provide a problem kernel
consisting of at most $(dp)^{p+1}+d$ vertices where each vertex has at most
$(dp)^{p}$ potential parent sets which can be computed in $(dp)^{{\omega
p}}\cdot|I|^{\mathcal{O}(1)}$ time. Observe that both, the running time and
the kernel size, are polynomial for every constant $p$. Note also that, since
$d+p\in\mathcal{O}(n)$, Theorem 3.2 implies that there is presumably no kernel
of size $(d+p)^{\mathcal{O}(1)}$ that can be computed in
$(d+p)^{\mathcal{O}(1)}$ time.

The basic idea of the kernelization is that we use max $q$-representations to
identify nondependent vertices that are not necessary to find a solution.

######  Theorem 5.9.

There is an algorithm that, given an instance $(N,\mathcal{F},t)$ of Polytree
Learning computes in time $(dp)^{\omega p}\cdot|I|^{\mathcal{O}(1)}$ an
equivalent instance $(N^{\prime},\mathcal{F}^{\prime},t)$ such that
$|N^{\prime}|\leq(dp)^{p+1}+d$ and
$\delta_{\mathcal{F}^{\prime}}\leq(dp)^{p}$.

###### Proof.

Let $H$ be the set of dependent verticesof $(N,\mathcal{F},t)$.

Computation of the reduced instance. We describe how we compute
$(N^{\prime},\mathcal{F}^{\prime},t)$. We define the family
$\mathcal{A}_{v}:=\\{P\times v\mid P\in\mathcal{P}_{\mathcal{F}}(v)\\}$ for
every $v\in H$ and the weight function
$w:\mathcal{A}_{v}\rightarrow\mathds{N}_{0}$ by $w(P\times v):=f_{v}(P)$. We
then apply the algorithm behind Theorem 5.3 $a)$ and compute a max
$((d-1)\cdot p)$-representing family $\widehat{\mathcal{A}}_{v}$ for every
$\mathcal{A}_{v}$.

Given all $\widehat{\mathcal{A}}_{v}$, a vertex $w$ is called _necessary_ if
$w\in H$ or if there exists some $v\in H$ such that $(w,v)\in A$ for some
$A\in\widehat{\mathcal{A}}_{v}$. We then define $N^{\prime}$ as the set of
necessary vertices. Next, $\mathcal{F}^{\prime}$ consists of local score
functions
$f_{v}^{\prime}:2^{N^{\prime}\setminus\\{v\\}}\rightarrow\mathds{N}_{0}$ with
$f_{v}^{\prime}(P):=f_{v}(P)$ for every $P\in 2^{N^{\prime}\setminus\\{v\\}}$.
In other words, $f_{v}^{\prime}$ is the limitation of $f_{v}$ on parent sets
that contain only necessary vertices.

Next, consider the running-time of the computation of
$(N^{\prime},\mathcal{F}^{\prime},t)$. Since each $\mathcal{A}_{v}$ contains
at most $\delta_{\mathcal{F}}$ arc sets and we assume that every potential
parent set has size exactly $p$, each $\widehat{\mathcal{A}}_{v}$ can be
computed in time

$\displaystyle\mathcal{O}\left(\binom{dp}{p}^{2}\cdot\delta_{\mathcal{F}}\cdot
p^{3}\cdot n^{2}+\delta_{\mathcal{F}}\cdot\binom{dp}{p}^{\omega}\cdot n\cdot
p\right)+(n+m)^{\mathcal{O}(1)}.$

Observe that we use the symmetry of the binomial coefficient to analyze this
running time. After computing all $\widehat{\mathcal{A}}_{v}$, we compute
$N^{\prime}$ and $\mathcal{F}^{\prime}$ in polynomial time in $|I|$. The
overall running time is $(dp)^{\omega p}\cdot|I|^{\mathcal{O}(1)}$.

Correctness. We next show that $(N,\mathcal{F},t)$ is a yes-instance if and
only if $(N^{\prime},\mathcal{F}^{\prime},t)$ is a yes-instance.

$(\Leftarrow)$ Let $(N^{\prime},\mathcal{F}^{\prime},t)$ be a yes-instance.
Then, there exists an arc-set $A^{\prime}$ such that $(N^{\prime},A^{\prime})$
is a polytree with score at least $t$. Since $N^{\prime}\subseteq N$,
$f_{v}^{\prime}(P)=f_{v}(P)$ for every $v\in N^{\prime}$, and $P\subseteq
N^{\prime}\setminus\\{v\\}$ we conclude that $(N,A^{\prime})$ is a polytree
with score at least $t$.

$(\Rightarrow)$ Let $(N,\mathcal{F},t)$ be a yes-instance. We choose a
solution $A$ for $(N,\mathcal{F},t)$ such that $P^{A}_{v}\subseteq N^{\prime}$
for as many dependent vertices $v$ as possible. We prove that this implies
that $P^{A}_{v}\subseteq N^{\prime}$ for all dependent vertices. Assume
towards a contradiction that there is some $v\in H$ with
$P^{A}_{v}\not\subseteq N^{\prime}$. Observe that $(P^{A}_{v}\times
v)\in\mathcal{A}_{v}\setminus\widehat{\mathcal{A}}_{v}$. We then define the
arc set $B:=\bigcup_{w\in H\setminus\\{v\\}}P^{A}_{w}\times w$. Since we
assume that all nonempty potential parent sets have size exactly $p$, we
conclude $|B|=(d-1)p$. Then, since $\widehat{\mathcal{A}}_{v}$ max
$((d-1)\cdot p)$-represents $\mathcal{A}_{v}$ and $(P^{A}_{v}\times
v)\in\mathcal{A}_{v}$ fits $B$ we conclude that there is some $(P\times
v)\in\widehat{\mathcal{A}}_{v}$ such that $B\cap(P\times v)=\emptyset$,
$(N,B\cap(P\times v))$ is a polytree, and $f_{v}(P)\geq f_{v}(P^{A}_{v})$.
Thus, $C:=B\cup(P\times v)$ is a solution of $(N,\mathcal{F},t)$ and the
number of vertices $v$ that satisfy $P^{C}_{v}\subseteq N^{\prime}$ is bigger
than the number of vertices $v$ that satisfy $P^{A}_{v}\subseteq N^{\prime}$.
This contradicts the choice of $A$.

Bound on the size of $|N^{\prime}|$ and $\delta_{\mathcal{F}^{\prime}}$. By
Theorem 5.3, each $\widehat{\mathcal{A}}_{i}$ has size at most
$\binom{(d-1)p+p}{p}=\binom{dp}{p}$. Consequently,
$\delta_{\mathcal{F}^{\prime}}\leq(dp)^{p}$ and $N^{\prime}\leq
d\cdot\binom{dp}{p}\cdot p+d\leq{(dp)^{p+1}+d}$. ∎

Observe that the instance $I:=(N^{\prime},\mathcal{F}^{\prime},t)$ from
Theorem 5.9 is technically not a kernel since the encoding of the integer $t$
and the values of $f_{v}(P)$ might not be bounded in $d$ and thus the size of
the instance $|I|$ is not bounded in $d$. We use the following lemma Etscheid
et al. (2017); Frank and Tardos (1987)to show that Theorem 5.9 implies an
actual polynomial kernel for the parameter $d$ when $p$ is constant.

######  Lemma 5.10 (Etscheid et al. (2017)).

There is an algorithm that, given a vector $w\in\mathds{Q}^{r}$ and some
$W\in\mathds{Q}$ computes in polynomial time a vector
$\overline{w}=(w_{1},\dots,w_{r})\in\mathds{Z}^{r}$ where
$\max_{i\in\\{1,\dots,r\\}}|w_{i}|\in 2^{\mathcal{O}(r^{3})}$ and an integer
$\overline{W}\in\mathds{Z}$ with total encoding length $\mathcal{O}(r^{4})$
such that $w\cdot x\geq W$ if and only if $\overline{w}\cdot
x\geq\overline{W}$ for every $x\in\\{0,1\\}^{r}$.

######  Corollary 5.11.

Polytree Learning with constant parent set size admits a polynomial kernel
when parameterized by $d$.

###### Proof.

Let $(N^{\prime},\mathcal{F}^{\prime},t)$ be the reduced instance from Theorem
5.9. Let $r$ be the number of triples $(P,|P|,f_{v}(P))$ in the two-
dimensional array representing $\mathcal{F}^{\prime}$. Clearly,
$r\leq|N^{\prime}|\cdot\delta_{\mathcal{F}^{\prime}}$. Let $w$ be the
$r$-dimensional vector containing all values $f_{v}(P)$ for all $v$ and $P$.
Applying the algorithm behind Lemma 5.10 on $w$ and $t$ computes a vector
$\overline{w}$ and an integer $\overline{t}$ that has encoding length
$\mathcal{O}((|N^{\prime}|\cdot\delta_{\mathcal{F}^{\prime}})^{4})$ with the
property stated in Lemma 5.10.

Substituting all local scores stored in $\mathcal{F}^{\prime}$ with the
corresponding values in $\overline{w}$ and substituting $t$ by $\overline{t}$
converts the instance $(N^{\prime},\mathcal{F}^{\prime},t)$ into an equivalent
instance which size is polynomially bounded in $d$ if $p$ is constant. ∎

##  6 Conclusion

We believe that there is potential for practically relevant exact Polytree
Learning algorithms and that this work could constitute a first step. Next,
one should aim for improved parameterizations. For example, Theorem 4.1 gives
an FPT algorithm for the parameter $\delta_{\mathcal{F}}+d$. Can we replace
$\delta_{\mathcal{F}}$ or $d$ by smaller parameters? Instead of
$\delta_{\mathcal{F}}$, one could consider parameters that are small when only
few dependent vertices have many potential parent sets. Instead of $d$, one
could consider parameters of the directed superstructure, for example the size
of a smallest vertex cover; this parameter never exceeds $d$. We think that
the algorithm with running time $3^{n}\cdot|I|^{\mathcal{O}(1)}$ might be
practical for $n$ up to 20 based on experience with dynamic programs with a
similar running time Komusiewicz et al. (2011). A next step should be to
combine this algorithm with heuristic data reduction and pruning rules to
further increase the range of tractable values of $n$.

## References

  * Bodlaender et al. (2011) Hans L. Bodlaender, Stéphan Thomassé, and Anders Yeo.  Kernel bounds for disjoint cycles and disjoint paths.  Theor. Comput. Sci., 412(35):4570–4578, 2011.
  * Chen et al. (2006) Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, and Ge Xia.  Strong computational lower bounds via parameterized complexity.  J. Comput. Syst. Sci., 72(8):1346–1367, 2006.
  * 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. Inf. Theory, 14(3):462–467, 1968.
  * 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.
  * Dasgupta (1999) Sanjoy Dasgupta.  Learning polytrees.  In Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence (UAI ’99), pages 134–141. Morgan Kaufmann, 1999.
  * Downey and Fellows (2013) Rodney G. Downey and Michael R. Fellows.  Fundamentals of Parameterized Complexity.  Texts in Computer Science. Springer, 2013.
  * Etscheid et al. (2017) Michael Etscheid, Stefan Kratsch, Matthias Mnich, and Heiko Röglin.  Polynomial kernels for weighted problems.  J. Comput. Syst. Sci., 84:1–10, 2017.
  * Fehri et al. (2019) Hamid Fehri, Ali Gooya, Yuanjun Lu, Erik Meijering, Simon A. Johnston, and Alejandro F. Frangi.  Bayesian polytrees with learned deep features for multi-class cell segmentation.  IEEE Trans. Image Process., 28(7):3246–3260, 2019.
  * Fomin et al. (2014) Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh.  Efficient computation of representative sets with applications in parameterized and exact algorithms.  In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’14), pages 142–151. SIAM, 2014.
  * Frank and Tardos (1987) András Frank and Éva Tardos.  An application of simultaneous diophantine approximation in combinatorial optimization.  Comb., 7(1):49–65, 1987.
  * 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 (2020a) Niels Grüttemeier and Christian Komusiewicz.  Learning Bayesian networks under sparsity constraints: A parameterized complexity analysis.  In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI ’20), pages 4245–4251. ijcai.org, 2020.
  * Grüttemeier and Komusiewicz (2020b) Niels Grüttemeier and Christian Komusiewicz.  On the relation of strong triadic closure and cluster deletion.  Algorithmica, 82(4):853–880, 2020.
  * Guo and Hsu (2002) Haipeng Guo and William Hsu.  A survey of algorithms for real-time Bayesian network inference.  In Working Notes of the Joint AAAI/UAI/KDD Workshop on Real-Time Decision Support and Diagnosis Systems, 2002.
  * Impagliazzo et al. (2001) Russell Impagliazzo, Ramamohan Paturi, and Francis Zane.  Which problems have strongly exponential complexity?  J. Comput. Syst. Sci., 63(4):512–530, 2001.
  * Komusiewicz et al. (2011) Christian Komusiewicz, Rolf Niedermeier, and Johannes Uhlmann.  Deconstructing intractability - A multivariate complexity analysis of interval constrained coloring.  J. Discrete Algorithms, 9(1):137–151, 2011.
  * 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.
  * Lokshtanov et al. (2018) Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, and Saket Saurabh.  Deterministic truncation of linear matroids.  ACM Trans. Algorithms, 14(2):14:1–14:20, 2018.
  * 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.
  * Pearl (1989) Judea Pearl.  Probabilistic reasoning in intelligent systems - networks of plausible inference.  Morgan Kaufmann series in representation and reasoning. Morgan Kaufmann, 1989.
  * Ramaswamy and Szeider (2021) Vaidyanathan Peruvemba Ramaswamy and Stefan Szeider.  Turbocharging treewidth-bounded Bayesian network structure learning.  In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI ’21), 2021.
  * Safaei et al. (2013) Javad Safaei, Ján Manuch, and Ladislav Stacho.  Learning polytrees with constant number of roots from data.  In Proceedings of the 26th Australasian Joint Conference on Advances in Artificial Intelligence (AI ’13), volume 8272 of Lecture Notes in Computer Science, pages 447–452. Springer, 2013.
  * Tutte (1965) William Thomas Tutte.  Lectures on matroids.  J. Research of the National Bureau of Standards (B), 69:1–47, 1965\.
  * van Beek and Hoffmann (2015) Peter van Beek and Hella-Franziska Hoffmann.  Machine learning of Bayesian networks using constraint programming.  In Proceedings of the twenty-first Conference of Principles and Practice of Constraint Programming (CP’15), volume 9255 of Lecture Notes in Computer Science, pages 429–445. Springer, 2015.
  * Williams (2012) Virginia Vassilevska Williams.  Multiplying matrices faster than coppersmith-winograd.  In Proceedings of the 44th Symposium on Theory of Computing Conference (STOC ’12), pages 887–898. ACM, 2012.