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