Sum-of-Products with Default Values: Algorithms and Complexity Results

Warning

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

GANIAN Robert KIM Eunjung SLIVOVSKY Friedrich SZEIDER Stefan

Year of publication 2018
Type Article in Proceedings
Conference IEEE 30th International Conference on Tools with Artificial Intelligence (ICTAI)
MU Faculty or unit

Faculty of Informatics

Citation
Doi http://dx.doi.org/10.1109/ICTAI.2018.00115
Keywords Sum of Products; Constraint Satisfaction; Boolean Satisfiability; Parameterized Complexity
Description Weighted Counting for Constraint Satisfaction with Default Values (#CSPD) is a powerful special case of the sum-of-products problem that admits succinct encodings of #CSP, #SAT, and inference in probabilistic graphical models. We investigate #CSPD under the fundamental parameter of incidence treewidth (i.e., the treewidth of the incidence graph of the constraint hypergraph). We show that if the incidence treewidth is bounded, then #CSPD can be solved in polynomial time. More specifically, we show that the problem is fixed-parameter tractable for the combined parameter incidence treewidth, domain size, and support size (the maximum number of non-default tuples in a constraint), generalizing a known result on the fixed-parameter tractability of #CSPD under the combined parameter primal treewidth and domain size. We further prove that the problem is not fixed-parameter tractable if any of the three components is dropped from the parameterization.
Related projects:

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