[Back]

St. Szeider:
"Parameterized Complexity Results for Probabilistic Network Structure Learning";
Keynote Lecture: Workshop on Applications of Parameterized Algorithms and Complexit, Warwick, UK (invited); 2012-07-08.

Probabilistic network structure learning is the notoriously difficult task of inferring probabilistic networks from data. A probabilistic network is a directed acyclic graph (DAG) whose vertices are labeled with certain tables that express probabilities. Under various goodness-of-fit measures, finding an optimal network is an NP-hard problem, even if restricted to polytrees. One of the very rare polynomial cases is due to Edmonds, who showed in a 1967 paper that an optimal branching (i.e., a polytree with maximum in-degree at most 1) can be inferred in polynomial time.

In this talk I will present some recent parameterized complexity results on probabilistic network structure learning with respect to various parameters, including the edit-distance of the inferred network from being a branching and the treewidth of the super-structure (a certain undirected graph that contains all the optimal networks). Further results that will be discussed concern the parameterized complexity of k-neighborhood local search, where the task is to improve the goodness-of-fit of a probabilistic network by reversing, deleting, or adding at most k arcs.

This is joint work with Serge Gaspers, Mathieu Liedloff, Mikko Koivisto, and Sebastian Ordyniak.

Project Head Stefan Szeider:
The Parameterized Complexity of Reasoning Problems