Talks and Poster Presentations (with Proceedings-Entry):
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.
English abstract:
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.
Related Projects:
Project Head Stefan Szeider:
Parametrisierte Komplexität Lokaler Suche
Project Head Stefan Szeider:
The Parameterized Complexity of Reasoning Problems
Created from the Publication Database of the Vienna University of Technology.