Publication details

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

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: