---
res:
bibo_abstract:
- "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.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Vladimir
foaf_name: Kolmogorov, Vladimir
foaf_surname: Kolmogorov
foaf_workInfoHomepage: http://www.librecat.org/personId=3D50B0BA-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Michal
foaf_name: Rolinek, Michal
foaf_surname: Rolinek
foaf_workInfoHomepage: http://www.librecat.org/personId=3CB3BC06-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Rustem
foaf_name: Takhanov, Rustem
foaf_surname: Takhanov
bibo_doi: 10.1007/978-3-662-48971-0_48
bibo_volume: 9472
dct_date: 2015^xs_gYear
dct_language: eng
dct_publisher: Springer@
dct_title: Effectiveness of structural restrictions for hybrid CSPs@
...