Backdoors into Heterogeneous Classes of SAT and CSP

D 2014

Backdoors into Heterogeneous Classes of SAT and CSP

GASPERS, Serge; Sebastian ORDYNIAK; Stefan SZEIDER; Neelhara MISRA; Stanislav ZIVNY et. al.

Základní údaje

Originální název

Backdoors into Heterogeneous Classes of SAT and CSP

Autoři

GASPERS, Serge; Sebastian ORDYNIAK; Stefan SZEIDER; Neelhara MISRA a Stanislav ZIVNY

Vydání

Quebec, AAAI Press, od s. 2652-2658, 7 s. 2014

Nakladatel

AAAI Press

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í

tištěná verze "print"

Odkazy

URL

Kód RIV

RIV/00216224:14330/14:00077721

Organizační jednotka

Fakulta informatiky

ISBN

978-1-57735-680-6

Klíčová slova anglicky

parameterized complexity;satisfiability; constraint satisfaction; strong backdoor; polymorphism

Štítky

core_A, firank_1

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 12. 5. 2020 19:51, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

Backdoor sets represent clever reasoning shortcuts through the search space for SAT and CSP. By instantiating the backdoor variables one reduces the given instance to several easy instances that belong to a tractable class.The overall time needed to solve the instance is exponential in the size of the backdoor set, hence it is a challenging problem to find a small backdoor set if one exists; over the last years this problem has been subject of intensive research. In this paper we extend the classical notion of a strong backdoor set by allowing that different instantiations of the backdoor variables result in instances that belong to different base classes; the union of the base classes forms a heterogeneous base class. Backdoor sets to heterogeneous base classes can be much smaller than backdoor sets to homogeneous ones, hence they are much more desirable but possibly harder to find. We draw a detailed complexity landscape for the problem of detecting strong backdoor sets into heterogeneous base classes for SAT and CSP. We provide algorithms that establish fixed-parameter tractability under natural parameterizations, and we contrast the tractability results with hardness results that pinpoint the theoretical limits. Our results apply to the current state-of-the-art of tractable classes of CSP and SAT that are definable by restricting the constraint language.

Návaznosti

EE2.3.30.0009, projekt VaV

Název: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci

Citovat

GASPERS, Serge; Sebastian ORDYNIAK; Stefan SZEIDER; Neelhara MISRA a Stanislav ZIVNY. Backdoors into Heterogeneous Classes of SAT and CSP. In Carla E. Brodley and Peter Stone. AAAI Press. Quebec: AAAI Press, 2014, s. 2652-2658. ISBN 978-1-57735-680-6.

@inproceedings{1212612,
   author = {Gaspers, Serge and Ordyniak, Sebastian and Szeider, Stefan and Misra, Neelhara and Zivny, Stanislav},
   address = {Quebec},
   booktitle = {AAAI Press},
   editor = {Carla E. Brodley and Peter Stone},
   keywords = {parameterized complexity;satisfiability; constraint satisfaction; strong backdoor; polymorphism},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Quebec},
   isbn = {978-1-57735-680-6},
   pages = {2652-2658},
   publisher = {AAAI Press},
   title = {Backdoors into Heterogeneous Classes of SAT and CSP},
   url = {https://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/view/8177},
   year = {2014}
}

TY  - CONF
ID  - 1212612
AU  - Gaspers, Serge - Ordyniak, Sebastian - Szeider, Stefan - Misra, Neelhara - Zivny, Stanislav
PY  - 2014
TI  - Backdoors into Heterogeneous Classes of SAT and CSP
PB  - AAAI Press
CY  - Quebec
SN  - 9781577356806
KW  - parameterized complexity;satisfiability
KW  - constraint satisfaction
KW  - strong backdoor
KW  - polymorphism
UR  - https://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/view/8177
N2  - Backdoor sets represent clever reasoning shortcuts through the search space for SAT and CSP. By instantiating the backdoor variables one reduces the given instance to several easy instances that belong to a tractable class.The overall time needed to solve the instance is exponential in the size of the backdoor set, hence it is a challenging problem to find a small backdoor set if one exists; over the last years this problem has been subject of intensive research. In this paper we extend the classical notion of a strong backdoor set by allowing that different instantiations of the backdoor variables result in instances that belong to different base classes; the union of the base classes forms a heterogeneous base class. Backdoor sets to heterogeneous base classes can be much smaller than backdoor sets to homogeneous ones, hence they are much more desirable but possibly harder to find. We draw a detailed complexity landscape for the problem of detecting strong backdoor sets into heterogeneous base classes for SAT and CSP. We provide algorithms that establish fixed-parameter tractability under natural parameterizations, and we contrast the tractability results with hardness results that pinpoint the theoretical limits. Our results apply to the current state-of-the-art of tractable classes of CSP and SAT that are definable by restricting the constraint language.
ER  -

GASPERS, Serge; Sebastian ORDYNIAK; Stefan SZEIDER; Neelhara MISRA a Stanislav ZIVNY. Backdoors into Heterogeneous Classes of SAT and CSP. In Carla E. Brodley and Peter Stone. \textit{AAAI Press}. Quebec: AAAI Press, 2014, s.~2652-2658. ISBN~978-1-57735-680-6.

Přehled o publikaci