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

GANIAN, Robert, Eunjung KIM, Friedrich SLIVOVSKY and Stefan SZEIDER. Sum-of-Products with Default Values: Algorithms and Complexity Results. Online. In Lefteri H. Tsoukalas, Eric Gregoire, Miltiadis Alamaniotis. IEEE 30th International Conference on Tools with Artificial Intelligence (ICTAI). USA: IEEE, 2018, p. 733-737. ISBN 978-1-5386-7449-9. Available from: https://dx.doi.org/10.1109/ICTAI.2018.00115.

Basic information

• Original name: Sum-of-Products with Default Values: Algorithms and Complexity Results
• Authors: GANIAN, Robert (203 Czech Republic, guarantor, belonging to the institution), Eunjung KIM (410 Republic of Korea), Friedrich SLIVOVSKY (40 Austria) and Stefan SZEIDER (40 Austria).
• Edition: USA, IEEE 30th International Conference on Tools with Artificial Intelligence (ICTAI), p. 733-737, 5 pp. 2018.
• Publisher: IEEE

Other information

• Original language: English
• Type of outcome: Proceedings paper
• Field of Study: 10201 Computer sciences, information science, bioinformatics
• Country of publisher: United States of America
• Confidentiality degree: is not subject to a state or trade secret
• Publication form: electronic version available online
• RIV identification code: RIV/00216224:14330/18:00106816
• Organization unit: Faculty of Informatics
• ISBN: 978-1-5386-7449-9
• ISSN: 1082-3409
• Doi: http://dx.doi.org/10.1109/ICTAI.2018.00115
• UT WoS: 000457750200105
• Keywords in English: Sum of Products; Constraint Satisfaction; Boolean Satisfiability; Parameterized Complexity
• Tags: core_B, firank_B
• Tags: International impact, Reviewed

Abstract

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.

Links

• MSM0021622419, plan (intention): Name: Vysoce paralelní a distribuované výpočetní systémy

Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems