Sum-of-Products with Default Values: Algorithms and Complexity Results
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F18%3A00106816" target="_blank" >RIV/00216224:14330/18:00106816 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1109/ICTAI.2018.00115" target="_blank" >http://dx.doi.org/10.1109/ICTAI.2018.00115</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1109/ICTAI.2018.00115" target="_blank" >10.1109/ICTAI.2018.00115</a>
Alternative languages
Result language
angličtina
Original language name
Sum-of-Products with Default Values: Algorithms and Complexity Results
Original language 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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2018
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
IEEE 30th International Conference on Tools with Artificial Intelligence (ICTAI)
ISBN
9781538674499
ISSN
1082-3409
e-ISSN
—
Number of pages
5
Pages from-to
733-737
Publisher name
IEEE
Place of publication
USA
Event location
Recko
Event date
Jul 5, 2018
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—