[Back]

S. Gaspers, Ej Kim, S. Ordyniak, S. Saurabh, St. Szeider:
"Don´t Be Strict in Local Search!";
Talk: AAAI Conference, Toronto, Ontario, Canada; 2012-07-22 - 2012-07-26; in: "Proceedings of the 26th Conference on Artificial Intelligence (AAAI 2012)", J. Hoffmann, B. Selman (ed.); AAAI Press, (2012), 486 - 492.

Inferring probabilistic networks from data is a notoriously difficult task. Under various goodness-of-fit measures, find- ing an optimal network is NP-hard, even if restricted to poly- trees of bounded in-degree. Polynomial-time algorithms are known only for rare special cases, perhaps most notably for branchings, that is, polytrees in which the in-degree of every node is at most one. Here, we study the complexity of find- ing an optimal polytree that can be turned into a branching by deleting some number of arcs or nodes, treated as a param- eter. We show that the problem can be solved via a matroid intersection formulation in polynomial time if the number of deleted arcs is bounded by a constant. The order of the poly- nomial time bound depends on this constant, hence the al- gorithm does not establish fixed-parameter tractability when parameterized by the number of deleted arcs. We show that a restricted version of the problem allows fixed-parameter tractability and hence scales well with the parameter. We con- trast this positive result by showing that if we parameterize by the number of deleted nodes, a somewhat more powerful pa- rameter, the problem is not fixed-parameter tractable, subject to a complexity-theoretic assumption.

Project Head Stefan Szeider:
Parametrisierte Komplexität Lokaler Suche

Project Head Stefan Szeider:
The Parameterized Complexity of Reasoning Problems