Hybrid VCSPs with crisp and valued conservative templates

DOI10.4230/LIPICS.ISAAC.2017.65zbMATH Open1457.68130MaRDI QIDQ5136286FDOQ5136286

Rustem Takhanov

Publication date: 25 November 2020

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

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)

Cites Work

• Existence theorems for weakly symmetric operations
• On the complexity of H-coloring
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures
• On the algebraic structure of combinatorial problems
• Domain permutation reduction for constraint satisfaction problems
• Complexity of conservative constraint satisfaction problems
• The complexity of conservative valued CSPs
• Hybrid tractability of valued constraint problems
• Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties.
• A strong Mal'cev condition for locally finite varieties omitting the unary type
• Title not available (Why is that?)
• Level of repair analysis and minimum cost homomorphisms of graphs
• Datalog and Constraint Satisfaction with Infinite Templates
• A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem
• On the hardness of approximating the chromatic number
• On the Reduction of the CSP Dichotomy Conjecture to Digraphs
• Title not available (Why is that?)
• Sherali-Adams Relaxations for Valued CSPs
• Effectiveness of Structural Restrictions for Hybrid CSPs

Cited In (1)

• Computing a partition function of a generalized pattern-based energy over a semiring

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)