A Join-Based Hybrid Parameter for Constraint Satisfaction

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

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

• Original language: English
• Type of outcome: Proceedings paper
• Field of Study: 10201 Computer sciences, information science, bioinformatics
• Country of publisher: United States of America
• Confidentiality degree: is not subject to a state or trade secret
• Publication form: electronic version available online
• WWW: 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: 0302-9743
• 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

Abstract

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.