Hybrid VCSPs with crisp and valued conservative templates

DOI10.4230/LIPICS.ISAAC.2017.65MaRDI QIDQ5136286zbMATH OpenFDO

Authors Rustem Takhanov

Publication date 25 November 2020

Full work available at URL https://doi.org/10.4230/LIPICS.ISAAC.2017.65

zbMATH Keywords

algebraic approachconstraint satisfaction problempolymorphismsclosed under inverse homomorphismshybrid CSPslifted language

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Relational systems, laws of composition (08A02) Applications of universal algebra in computer science (08A70) Computational aspects of satisfiability (68R07)

Recommendations

• Effectiveness of structural restrictions for hybrid CSPs
• Hybrid tractable classes of constraint problems
• Hybrid tractability of valued constraint problems
• Asking the Metaquestions in Constraint Tractability
• CSP for binary conservative relational structures

Cites work

• scientific article; zbMATH DE number 2062604 (Why is no real title available?)
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• A dichotomy theorem for the general minimum cost homomorphism problem
• A strong Mal'cev condition for locally finite varieties omitting the unary type
• Classifying the Complexity of Constraints Using Finite Algebras
• Complexity of conservative constraint satisfaction problems
• Datalog and Constraint Satisfaction with Infinite Templates
• Domain permutation reduction for constraint satisfaction problems
• Effectiveness of structural restrictions for hybrid CSPs
• Existence theorems for weakly symmetric operations
• Hybrid tractability of valued constraint problems
• Level of repair analysis and minimum cost homomorphisms of graphs
• On the algebraic structure of combinatorial problems
• On the complexity of H-coloring
• On the hardness of approximating the chromatic number
• On the reduction of the CSP dichotomy conjecture to digraphs
• Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties.
• Sherali-Adams relaxations for valued CSPs
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The complexity of conservative valued CSPs
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures
• The complexity of valued constraint satisfaction

Cited in

(4)

• Hybrid tractability of valued constraint problems
• Computing a partition function of a generalized pattern-based energy over a semiring
• Hybrid tractable classes of constraint problems
• Effectiveness of structural restrictions for hybrid CSPs

This page was built for publication: Hybrid VCSPs with crisp and valued conservative templates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136286)