[Back]

S. Ordyniak, St. Szeider:
"Parameterized Complexity Results for Exact Bayesian Network Structure Learning";
Journal of Artificial Intelligence Research, 46 (2013), 263 - 302.

Bayesian network structure learning is the notoriously difficult
problem of discovering a Bayesian network that optimally represents a
given set of training data. In this paper we study the computational
worst-case complexity of exact Bayesian network structure learning
under graph theoretic restrictions on the (directed)
super-structure. The super-structure is an undirected graph that
contains as subgraphs the skeletons of solution networks. We introduce
the directed super-structure as a natural generalization of its
undirected counterpart. Our results apply to several variants of
score-based Bayesian network structure learning where the score of a
network decomposes into local scores of its nodes. Results: We show
that exact Bayesian network structure learning can be carried out in
non-uniform polynomial time if the super-structure has bounded
treewidth, and in linear time if in addition the super-structure has
bounded maximum degree. Furthermore, we show that if the directed
super-structure is acyclic, then exact Bayesian network structure
learning can be carried out in quadratic time. We complement these
positive results with a number of hardness results. We show that both
restrictions (treewidth and degree) are essential and cannot be
dropped without loosing uniform polynomial time tractability (subject
to a complexity-theoretic assumption). Similarly, exact Bayesian
network struc- ture learning remains NP-hard for "almost acyclic"
directed super-structures. Furthermore, we show that the restrictions
remain essential if we do not search for a globally optimal network
but aim to improve a given network by means of at most k arc
additions, arc deletions, or arc reversals (k-neighborhood local
search).

algorithms, complexity, machine learning

http://dx.doi.org/10.1613/jair.3744

Project Head Stefan Szeider:
The Parameterized Complexity of Reasoning Problems