Sum-of-Products with Default Values: Algorithms and Complexity Results
| Autoři | |
|---|---|
| Rok publikování | 2018 |
| Druh | Článek ve sborníku |
| Konference | IEEE 30th International Conference on Tools with Artificial Intelligence (ICTAI) |
| Fakulta / Pracoviště MU | |
| Citace | |
| Doi | http://dx.doi.org/10.1109/ICTAI.2018.00115 |
| Klíčová slova | Sum of Products; Constraint Satisfaction; Boolean Satisfiability; Parameterized Complexity |
| Popis | 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. |
| Související projekty: |