Titre : Homomorphism Problems and Approximation Algorithm
Exposant :  Arash Rafiey

Résumé : Several combinatorial optimization problems can be formulated as a 
homomorphism problem. The homomorphism problem seeks for a 
structure-preserving mapping from an input graph (digraph) to a fixed 
target graph (digraph). If for mapping each vertex of the input graph to
the target graph there is an associated cost then we get an optimization
version of the problem so called minimum cost homomorphism. The goal is to
map the input graph to the target graph with the minimum cost. The minimum
cost homomorphism problem is motivated by a real-world problem in defense
logistics. 

If the target graph (digraph) H has a special combinatorial structure
(special ordering) then the homomorphism problem is polynomial time
solvable. We talk about an approximation algorithm for the minimum cost
homomorphism problem and we mention new results and open problems.