A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem
From MaRDI portal
Publication:3113788
DOI10.4230/LIPIcs.STACS.2010.2493zbMath1230.90192MaRDI QIDQ3113788
Publication date: 23 January 2012
Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_30bf.html
supervised learning; perfect graphs; constraint satisfaction problem; relational clones; minimum cost homomorphisms problem
Related Items
Unnamed Item, Unnamed Item, The Complexity of Valued CSPs, The Complexity of General-Valued CSPs, The Power of Sherali--Adams Relaxations for General-Valued CSPs, Binarisation for Valued Constraint Satisfaction Problems, Unnamed Item, PTAS for Sparse General-valued CSPs, Hybrid tractability of valued constraint problems, The complexity of approximating conservative counting CSPs, Variable and value elimination in binary constraint satisfaction via forbidden patterns, On planar valued CSPs, An application of Farkas' lemma to finite-valued constraint satisfaction problems over infinite domains, Minimum Cost Homomorphisms with Constrained Costs, Sherali-Adams Relaxations for Valued CSPs, Necessary Conditions for Tractability of Valued CSPs