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

D 2018

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

GANIAN, Robert, Eunjung KIM, Friedrich SLIVOVSKY and Stefan SZEIDER

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

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United States of America

Confidentiality degree

není předmětem státního či obchodního tajemství

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

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

Abstract

V originále

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

Citovat

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.

@inproceedings{1523797,
   author = {Ganian, Robert and Kim, Eunjung and Slivovsky, Friedrich and Szeider, Stefan},
   address = {USA},
   booktitle = {IEEE 30th International Conference on Tools with Artificial Intelligence (ICTAI)},
   doi = {http://dx.doi.org/10.1109/ICTAI.2018.00115},
   editor = {Lefteri H. Tsoukalas, Eric Gregoire, Miltiadis Alamaniotis},
   keywords = {Sum of Products; Constraint Satisfaction; Boolean Satisfiability; Parameterized Complexity},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {USA},
   isbn = {978-1-5386-7449-9},
   pages = {733-737},
   publisher = {IEEE},
   title = {Sum-of-Products with Default Values: Algorithms and Complexity Results},
   year = {2018}
}

TY  - JOUR
ID  - 1523797
AU  - Ganian, Robert - Kim, Eunjung - Slivovsky, Friedrich - Szeider, Stefan
PY  - 2018
TI  - Sum-of-Products with Default Values: Algorithms and Complexity Results
PB  - IEEE
CY  - USA
SN  - 9781538674499
KW  - Sum of Products
KW  - Constraint Satisfaction
KW  - Boolean Satisfiability
KW  - Parameterized Complexity
N2  - 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.
ER  -

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. \textit{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.

Detailed Information on Publication Record