D 2019

A Join-Based Hybrid Parameter for Constraint Satisfaction

GANIAN, Robert, Sebastian ORDYNIAK and Stefan SZEIDER

Basic information

Original name

A Join-Based Hybrid Parameter for Constraint Satisfaction

Authors

GANIAN, Robert (203 Czech Republic, guarantor, belonging to the institution), Sebastian ORDYNIAK (276 Germany) and Stefan SZEIDER (40 Austria)

Edition

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

Publisher

Springer

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

References:

URL

Impact factor

Impact factor: 0.402 in 2005

RIV identification code

RIV/00216224:14330/19:00113721

Organization unit

Faculty of Informatics

ISBN

978-3-030-30047-0

ISSN

DOI

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

UT WoS

000560404200012

Keywords in English

Parameterized Complexity

Tags

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

Abstract

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.
Displayed: 5/11/2024 07:02