A Join-Based Hybrid Parameter for Constraint Satisfaction

D 2019

A Join-Based Hybrid Parameter for Constraint Satisfaction

GANIAN, Robert, Sebastian ORDYNIAK a Stefan SZEIDER

Základní údaje

Originální název

A Join-Based Hybrid Parameter for Constraint Satisfaction

Autoři

GANIAN, Robert (203 Česká republika, garant, domácí), Sebastian ORDYNIAK (276 Německo) a Stefan SZEIDER (40 Rakousko)

Vydání

USA, Principles and Practice of Constraint Programming - 25th International Conference, od s. 195-212, 18 s. 2019

Nakladatel

Springer

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"

Odkazy

URL

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/19:00113721

Organizační jednotka

Fakulta informatiky

ISBN

978-3-030-30047-0

ISSN

DOI

http://dx.doi.org/10.1007/978-3-030-30048-7_12

UT WoS

000560404200012

Klíčová slova anglicky

Parameterized Complexity

Štítky

core_A, firank_A

Změněno: 16. 5. 2022 14:29, Mgr. Michal Petr

Anotace

V originále

We propose joinwidth, a new complexity parameter for the Constraint Satisfaction Problem (CSP). The definition of joinwidth is based on the arrangement of basic operations on relations (joins, projections, and pruning), which inherently reflects the steps required to solve the instance. We use joinwidth to obtain polynomial-time algorithms (if a corresponding decomposition is provided in the input) as well as fixed-parameter algorithms (if no such decomposition is provided) for solving the CSP. Joinwidth is a hybrid parameter, as it takes both the graphical structure as well as the constraint relations that appear in the instance into account. It has, therefore, the potential to capture larger classes of tractable instances than purely structural parameters like hypertree width and the more general fractional hypertree width (fhtw). Indeed, we show that any class of instances of bounded fhtw also has bounded joinwidth, and that there exist classes of instances of bounded joinwidth and unbounded fhtw, so bounded joinwidth properly generalizes bounded fhtw. We further show that bounded joinwidth also properly generalizes several other known hybrid restrictions, such as fhtw with degree constraints and functional dependencies. In this sense, bounded joinwidth can be seen as a unifying principle that explains the tractability of several seemingly unrelated classes of CSP instances.

Citovat

GANIAN, Robert, Sebastian ORDYNIAK a Stefan SZEIDER. A Join-Based Hybrid Parameter for Constraint Satisfaction. Online. In Thomas Schiex and Simon de Givry. Principles and Practice of Constraint Programming - 25th International Conference. USA: Springer, 2019, s. 195-212. ISBN 978-3-030-30047-0. Dostupné z: https://dx.doi.org/10.1007/978-3-030-30048-7_12.

@inproceedings{1648256,
   author = {Ganian, Robert and Ordyniak, Sebastian and Szeider, Stefan},
   address = {USA},
   booktitle = {Principles and Practice of Constraint Programming - 25th International Conference},
   doi = {http://dx.doi.org/10.1007/978-3-030-30048-7_12},
   editor = {Thomas Schiex and Simon de Givry},
   keywords = {Parameterized Complexity},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {USA},
   isbn = {978-3-030-30047-0},
   pages = {195-212},
   publisher = {Springer},
   title = {A Join-Based Hybrid Parameter for Constraint Satisfaction},
   url = {https://link.springer.com/chapter/10.1007%2F978-3-030-30048-7_12},
   year = {2019}
}

TY  - JOUR
ID  - 1648256
AU  - Ganian, Robert - Ordyniak, Sebastian - Szeider, Stefan
PY  - 2019
TI  - A Join-Based Hybrid Parameter for Constraint Satisfaction
PB  - Springer
CY  - USA
SN  - 9783030300470
KW  - Parameterized Complexity
UR  - https://link.springer.com/chapter/10.1007%2F978-3-030-30048-7_12
L2  - https://link.springer.com/chapter/10.1007%2F978-3-030-30048-7_12
N2  - We propose joinwidth, a new complexity parameter for the Constraint Satisfaction Problem (CSP). The definition of joinwidth is based on the arrangement of basic operations on relations (joins, projections, and pruning), which inherently reflects the steps required to solve the instance. We use joinwidth to obtain polynomial-time algorithms (if a corresponding decomposition is provided in the input) as well as fixed-parameter algorithms (if no such decomposition is provided) for solving the CSP. Joinwidth is a hybrid parameter, as it takes both the graphical structure as well as the constraint relations that appear in the instance into account. It has, therefore, the potential to capture larger classes of tractable instances than purely structural parameters like hypertree width and the more general fractional hypertree width (fhtw). Indeed, we show that any class of instances of bounded fhtw also has bounded joinwidth, and that there exist classes of instances of bounded joinwidth and unbounded fhtw, so bounded joinwidth properly generalizes bounded fhtw. We further show that bounded joinwidth also properly generalizes several other known hybrid restrictions, such as fhtw with degree constraints and functional dependencies. In this sense, bounded joinwidth can be seen as a unifying principle that explains the tractability of several seemingly unrelated classes of CSP instances.
ER  -

GANIAN, Robert, Sebastian ORDYNIAK a Stefan SZEIDER. A Join-Based Hybrid Parameter for Constraint Satisfaction. Online. In Thomas Schiex and Simon de Givry. \textit{Principles and Practice of Constraint Programming - 25th International Conference}. USA: Springer, 2019, s.~195-212. ISBN~978-3-030-30047-0. Dostupné z: https://dx.doi.org/10.1007/978-3-030-30048-7\_{}12.

Podrobný výpis o publikaci