Parameterized Complexity Results for Exact Bayesian Network Structure Learning

Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

ORDYNIAK Sebastian SZEIDER Stefan

Year of publication 2013
Type Article in Periodical
Magazine / Source JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH
MU Faculty or unit

Faculty of Informatics

Citation
Doi http://dx.doi.org/10.1613/jair.3744
Field Information theory
Keywords probabilistic network structure learning; parameterized complexity;algorithms
Description The propositional planning problem is a notoriously difficult computational problem, which remains hard even under strong syntactical and structural restrictions. Given its difficulty it becomes natural to study planning in the context of parameterized complexity. In this paper we continue the work initiated by Downey, Fellows and Stege on the parameterized complexity of planning with respect to the parameter ``length of the solution plan.'' We provide a complete classification of the parameterized complexity of the planning problem under two of the most prominent syntactical restrictions, i.e., the so called PUBS restrictions introduced by B{\"a}ckstr\"{o}m and Nebel and restrictions on the number of preconditions and effects as introduced by Bylander. We also determine which of the considered fixed-parameter tractable problems admit a polynomial kernel and which don't.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.