---
_id: '1636'
abstract:
- lang: eng
  text: "Constraint Satisfaction Problem (CSP) is a fundamental algorithmic problem
    that appears in many areas of Computer Science. It can be equivalently stated
    as computing a homomorphism R→ΓΓ between two relational structures, e.g. between
    two directed graphs. Analyzing its complexity has been a prominent research direction,
    especially for the fixed template CSPs where the right side ΓΓ is fixed and the
    left side R is unconstrained.\r\n\r\nFar fewer results are known for the hybrid
    setting that restricts both sides simultaneously. It assumes that R belongs to
    a certain class of relational structures (called a structural restriction in this
    paper). We study which structural restrictions are effective, i.e. there exists
    a fixed template ΓΓ (from a certain class of languages) for which the problem
    is tractable when R is restricted, and NP-hard otherwise. We provide a characterization
    for structural restrictions that are closed under inverse homomorphisms. The criterion
    is based on the chromatic number of a relational structure defined in this paper;
    it generalizes the standard chromatic number of a graph.\r\n\r\nAs our main tool,
    we use the algebraic machinery developed for fixed template CSPs. To apply it
    to our case, we introduce a new construction called a “lifted language”. We also
    give a characterization for structural restrictions corresponding to minor-closed
    families of graphs, extend results to certain Valued CSPs (namely conservative
    valued languages), and state implications for (valued) CSPs with ordered variables
    and for the maximum weight independent set problem on some restricted families
    of graphs."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Vladimir
  full_name: Kolmogorov, Vladimir
  id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
  last_name: Kolmogorov
- first_name: Michal
  full_name: Rolinek, Michal
  id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
  last_name: Rolinek
- first_name: Rustem
  full_name: Takhanov, Rustem
  last_name: Takhanov
citation:
  ama: 'Kolmogorov V, Rolinek M, Takhanov R. Effectiveness of structural restrictions
    for hybrid CSPs. In: <i>26th International Symposium</i>. Vol 9472. Springer Nature;
    2015:566-577. doi:<a href="https://doi.org/10.1007/978-3-662-48971-0_48">10.1007/978-3-662-48971-0_48</a>'
  apa: 'Kolmogorov, V., Rolinek, M., &#38; Takhanov, R. (2015). Effectiveness of structural
    restrictions for hybrid CSPs. In <i>26th International Symposium</i> (Vol. 9472,
    pp. 566–577). Nagoya, Japan: Springer Nature. <a href="https://doi.org/10.1007/978-3-662-48971-0_48">https://doi.org/10.1007/978-3-662-48971-0_48</a>'
  chicago: Kolmogorov, Vladimir, Michal Rolinek, and Rustem Takhanov. “Effectiveness
    of Structural Restrictions for Hybrid CSPs.” In <i>26th International Symposium</i>,
    9472:566–77. Springer Nature, 2015. <a href="https://doi.org/10.1007/978-3-662-48971-0_48">https://doi.org/10.1007/978-3-662-48971-0_48</a>.
  ieee: V. Kolmogorov, M. Rolinek, and R. Takhanov, “Effectiveness of structural restrictions
    for hybrid CSPs,” in <i>26th International Symposium</i>, Nagoya, Japan, 2015,
    vol. 9472, pp. 566–577.
  ista: 'Kolmogorov V, Rolinek M, Takhanov R. 2015. Effectiveness of structural restrictions
    for hybrid CSPs. 26th International Symposium. ISAAC: International Symposium
    on Algorithms and Computation, LNCS, vol. 9472, 566–577.'
  mla: Kolmogorov, Vladimir, et al. “Effectiveness of Structural Restrictions for
    Hybrid CSPs.” <i>26th International Symposium</i>, vol. 9472, Springer Nature,
    2015, pp. 566–77, doi:<a href="https://doi.org/10.1007/978-3-662-48971-0_48">10.1007/978-3-662-48971-0_48</a>.
  short: V. Kolmogorov, M. Rolinek, R. Takhanov, in:, 26th International Symposium,
    Springer Nature, 2015, pp. 566–577.
conference:
  end_date: 2015-12-11
  location: Nagoya, Japan
  name: 'ISAAC: International Symposium on Algorithms and Computation'
  start_date: 2015-12-09
date_created: 2018-12-11T11:53:10Z
date_published: 2015-12-01T00:00:00Z
date_updated: 2022-02-01T15:12:35Z
day: '01'
department:
- _id: VlKo
doi: 10.1007/978-3-662-48971-0_48
ec_funded: 1
external_id:
  arxiv:
  - '1504.07067'
intvolume: '      9472'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1504.07067
month: '12'
oa: 1
oa_version: Preprint
page: 566 - 577
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '616160'
  name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: 26th International Symposium
publication_identifier:
  isbn:
  - 978-3-662-48970-3
publication_status: published
publisher: Springer Nature
publist_id: '5519'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Effectiveness of structural restrictions for hybrid CSPs
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 9472
year: '2015'
...