Efficient Bayesian Network Structure Learning via Parameterized Local
  Search on Topological Orderings
  In Bayesian Network Structure Learning (BNSL), one is given a variable set
and parent scores for each variable and aims to compute a DAG, called Bayesian
network, that maximizes the sum of parent scores, possibly under some
structural constraints. Even very restricted special cases of BNSL are
computationally hard, and, thus, in practice heuristics such as local search
are used. A natural approach for a local search algorithm is a hill climbing
strategy, where one replaces a given BNSL solution by a better solution within
some pre-defined neighborhood as long as this is possible. We study
ordering-based local search, where a solution is described via a topological
ordering of the variables. We show that given such a topological ordering, one
can compute an optimal DAG whose ordering is within inversion distance $r$ in
subexponential FPT time; the parameter $r$ allows to balance between solution
quality and running time of the local search algorithm. This running time bound
can be achieved for BNSL without structural constraints and for all structural
constraints that can be expressed via a sum of weights that are associated with
each parent set. We also introduce a related distance called `window inversions
distance' and show that the corresponding local search problem can also be
solved in subexponential FPT time for the parameter $r$. For two further
natural modification operations on the variable orderings, we show that
algorithms with an FPT time for $r$ are unlikely. We also outline the limits of
ordering-based local search by showing that it cannot be used for common
structural constraints on the moralized graph of the network.
