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 a Stefan SZEIDER

Základní údaje

Originální název

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

Autoři

GANIAN, Robert (203 Česká republika, garant, domácí), Eunjung KIM (410 Korejská republika), Friedrich SLIVOVSKY (40 Rakousko) a Stefan SZEIDER (40 Rakousko)

Vydání

USA, IEEE 30th International Conference on Tools with Artificial Intelligence (ICTAI), od s. 733-737, 5 s. 2018

Nakladatel

IEEE

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

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

Forma vydání

elektronická verze "online"

Kód RIV

RIV/00216224:14330/18:00106816

Organizační jednotka

Fakulta informatiky

ISBN

978-1-5386-7449-9

ISSN

DOI

http://dx.doi.org/10.1109/ICTAI.2018.00115

UT WoS

000457750200105

Klíčová slova anglicky

Sum of Products; Constraint Satisfaction; Boolean Satisfiability; Parameterized Complexity

Štítky

core_B, firank_B

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 31. 5. 2022 12:21, RNDr. Pavel Šmerk, Ph.D.

Anotace

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.

Návaznosti

MSM0021622419, záměr

Název: Vysoce paralelní a distribuované výpočetní systémy

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy

Citovat

GANIAN, Robert, Eunjung KIM, Friedrich SLIVOVSKY a 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, s. 733-737. ISBN 978-1-5386-7449-9. Dostupné z: 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 a 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, s.~733-737. ISBN~978-1-5386-7449-9. Dostupné z: https://dx.doi.org/10.1109/ICTAI.2018.00115.

Podrobný výpis o publikaci