Hybrid VCSPs with crisp and valued conservative templates

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A constraint satisfaction problem (CSP) is a problem of computing a homomorphism R between two relational structures, e.g. between two directed graphs. Analyzing its complexity has been a very fruitful research direction, especially for fixed template CSPs (or, non-uniform CSPs), denoted CSP in which the right side structure is fixed and the left side structure R is unconstrained. Recently, the hybrid setting, written CSPH where both sides are restricted simultaneously, attracted some attention. It assumes that R is taken from a class of relational structures H (called the structural restriction) that additionally is closed under inverse homomorphisms. The last property allows to exploit an algebraic machinery that has been developed for fixed template CSPs. The key concept that connects hybrid CSPs with fixed-Template CSPs is the so called "lifted language". Namely, this is a constraint language R that can be constructed from an input R. The tractability of the language R for any input R 2 H is a necessary condition for the tractability of the hybrid problem. In the first part we investigate templates for which the latter condition is not only necessary, but also is sufficient. We call such templates widely tractable. For this purpose, we construct from a new finite relational structure 0 and define a "maximal" structural restriction H0 as a class of structures homomorphic to 0. For the so called strongly BJK templates that probably captures all templates, we prove that wide tractability is equivalent to the tractability of CSPH0 Our proof is based on the key observation that R is homomorphic to if and only if the core of R is preserved by a Siggers polymorphism. Analogous result is shown for conservative valued CSPs.

Original languageEnglish
Title of host publication28th International Symposium on Algorithms and Computation, ISAAC 2017
EditorsTakeshi Tokuyama, Yoshio Okamoto
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volume92
ISBN (Electronic)9783959770545
DOIs
Publication statusPublished - Dec 1 2017
Event28th International Symposium on Algorithms and Computation, ISAAC 2017 - Phuket, Thailand
Duration: Dec 9 2017Dec 22 2017

Conference

Conference28th International Symposium on Algorithms and Computation, ISAAC 2017
CountryThailand
CityPhuket
Period12/9/1712/22/17

Fingerprint

Constraint satisfaction problems
Directed graphs
Polymorphism
Machinery

Keywords

  • Algebraic approach
  • Closed under inverse homomorphisms
  • Constraint satisfaction problem
  • Hybrid CSPS
  • Lifted language
  • Polymorphisms

ASJC Scopus subject areas

  • Software

Cite this

Takhanov, R. (2017). Hybrid VCSPs with crisp and valued conservative templates. In T. Tokuyama, & Y. Okamoto (Eds.), 28th International Symposium on Algorithms and Computation, ISAAC 2017 (Vol. 92). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ISAAC.2017.65

Hybrid VCSPs with crisp and valued conservative templates. / Takhanov, Rustem.

28th International Symposium on Algorithms and Computation, ISAAC 2017. ed. / Takeshi Tokuyama; Yoshio Okamoto. Vol. 92 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Takhanov, R 2017, Hybrid VCSPs with crisp and valued conservative templates. in T Tokuyama & Y Okamoto (eds), 28th International Symposium on Algorithms and Computation, ISAAC 2017. vol. 92, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 28th International Symposium on Algorithms and Computation, ISAAC 2017, Phuket, Thailand, 12/9/17. https://doi.org/10.4230/LIPIcs.ISAAC.2017.65
Takhanov R. Hybrid VCSPs with crisp and valued conservative templates. In Tokuyama T, Okamoto Y, editors, 28th International Symposium on Algorithms and Computation, ISAAC 2017. Vol. 92. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2017 https://doi.org/10.4230/LIPIcs.ISAAC.2017.65
Takhanov, Rustem. / Hybrid VCSPs with crisp and valued conservative templates. 28th International Symposium on Algorithms and Computation, ISAAC 2017. editor / Takeshi Tokuyama ; Yoshio Okamoto. Vol. 92 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017.
@inproceedings{07c5528bdd464c139a3cfee87c50b379,
title = "Hybrid VCSPs with crisp and valued conservative templates",
abstract = "A constraint satisfaction problem (CSP) is a problem of computing a homomorphism R between two relational structures, e.g. between two directed graphs. Analyzing its complexity has been a very fruitful research direction, especially for fixed template CSPs (or, non-uniform CSPs), denoted CSP in which the right side structure is fixed and the left side structure R is unconstrained. Recently, the hybrid setting, written CSPH where both sides are restricted simultaneously, attracted some attention. It assumes that R is taken from a class of relational structures H (called the structural restriction) that additionally is closed under inverse homomorphisms. The last property allows to exploit an algebraic machinery that has been developed for fixed template CSPs. The key concept that connects hybrid CSPs with fixed-Template CSPs is the so called {"}lifted language{"}. Namely, this is a constraint language R that can be constructed from an input R. The tractability of the language R for any input R 2 H is a necessary condition for the tractability of the hybrid problem. In the first part we investigate templates for which the latter condition is not only necessary, but also is sufficient. We call such templates widely tractable. For this purpose, we construct from a new finite relational structure 0 and define a {"}maximal{"} structural restriction H0 as a class of structures homomorphic to 0. For the so called strongly BJK templates that probably captures all templates, we prove that wide tractability is equivalent to the tractability of CSPH0 Our proof is based on the key observation that R is homomorphic to if and only if the core of R is preserved by a Siggers polymorphism. Analogous result is shown for conservative valued CSPs.",
keywords = "Algebraic approach, Closed under inverse homomorphisms, Constraint satisfaction problem, Hybrid CSPS, Lifted language, Polymorphisms",
author = "Rustem Takhanov",
year = "2017",
month = "12",
day = "1",
doi = "10.4230/LIPIcs.ISAAC.2017.65",
language = "English",
volume = "92",
editor = "Takeshi Tokuyama and Yoshio Okamoto",
booktitle = "28th International Symposium on Algorithms and Computation, ISAAC 2017",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
address = "Germany",

}

TY - GEN

T1 - Hybrid VCSPs with crisp and valued conservative templates

AU - Takhanov, Rustem

PY - 2017/12/1

Y1 - 2017/12/1

N2 - A constraint satisfaction problem (CSP) is a problem of computing a homomorphism R between two relational structures, e.g. between two directed graphs. Analyzing its complexity has been a very fruitful research direction, especially for fixed template CSPs (or, non-uniform CSPs), denoted CSP in which the right side structure is fixed and the left side structure R is unconstrained. Recently, the hybrid setting, written CSPH where both sides are restricted simultaneously, attracted some attention. It assumes that R is taken from a class of relational structures H (called the structural restriction) that additionally is closed under inverse homomorphisms. The last property allows to exploit an algebraic machinery that has been developed for fixed template CSPs. The key concept that connects hybrid CSPs with fixed-Template CSPs is the so called "lifted language". Namely, this is a constraint language R that can be constructed from an input R. The tractability of the language R for any input R 2 H is a necessary condition for the tractability of the hybrid problem. In the first part we investigate templates for which the latter condition is not only necessary, but also is sufficient. We call such templates widely tractable. For this purpose, we construct from a new finite relational structure 0 and define a "maximal" structural restriction H0 as a class of structures homomorphic to 0. For the so called strongly BJK templates that probably captures all templates, we prove that wide tractability is equivalent to the tractability of CSPH0 Our proof is based on the key observation that R is homomorphic to if and only if the core of R is preserved by a Siggers polymorphism. Analogous result is shown for conservative valued CSPs.

AB - A constraint satisfaction problem (CSP) is a problem of computing a homomorphism R between two relational structures, e.g. between two directed graphs. Analyzing its complexity has been a very fruitful research direction, especially for fixed template CSPs (or, non-uniform CSPs), denoted CSP in which the right side structure is fixed and the left side structure R is unconstrained. Recently, the hybrid setting, written CSPH where both sides are restricted simultaneously, attracted some attention. It assumes that R is taken from a class of relational structures H (called the structural restriction) that additionally is closed under inverse homomorphisms. The last property allows to exploit an algebraic machinery that has been developed for fixed template CSPs. The key concept that connects hybrid CSPs with fixed-Template CSPs is the so called "lifted language". Namely, this is a constraint language R that can be constructed from an input R. The tractability of the language R for any input R 2 H is a necessary condition for the tractability of the hybrid problem. In the first part we investigate templates for which the latter condition is not only necessary, but also is sufficient. We call such templates widely tractable. For this purpose, we construct from a new finite relational structure 0 and define a "maximal" structural restriction H0 as a class of structures homomorphic to 0. For the so called strongly BJK templates that probably captures all templates, we prove that wide tractability is equivalent to the tractability of CSPH0 Our proof is based on the key observation that R is homomorphic to if and only if the core of R is preserved by a Siggers polymorphism. Analogous result is shown for conservative valued CSPs.

KW - Algebraic approach

KW - Closed under inverse homomorphisms

KW - Constraint satisfaction problem

KW - Hybrid CSPS

KW - Lifted language

KW - Polymorphisms

UR - http://www.scopus.com/inward/record.url?scp=85038592553&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85038592553&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ISAAC.2017.65

DO - 10.4230/LIPIcs.ISAAC.2017.65

M3 - Conference contribution

AN - SCOPUS:85038592553

VL - 92

BT - 28th International Symposium on Algorithms and Computation, ISAAC 2017

A2 - Tokuyama, Takeshi

A2 - Okamoto, Yoshio

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

ER -