# Seminar: The Graph Homomorphism Problem and its Applications

**Arash Rafiey****Department of Math and Computer Science****Indiana State University**

*The Graph Homomorphism Problem and its Applications*

Department of Computer Science

Tuesday, February 28, 2017, 12:00 p.m., Room EN-2022

**Abstract**

The homomorphism problem is a generalization of the graph coloring problem. A mapping f from V(G) to V(H) is a homomorphism of G to H if for any edge uv of G, the pair f(u)f(v) is an edge of H.

In the optimization version of this problem, for each pair u in V(G) and i in V(H) there is a cost of mapping u to i. The cost of a homomorphism f from G to H is the sum of the cost of the pairs u, f(u), over the vertices u of G. The minimum cost homomorphism problem, MinHOM(H), seeks a homomorphism f from G to H with minimum cost.

We first present some applications of this problem. Using the network min-cut algorithm, we show how to solve the problem efficiently in some special cases.

We survey the results in this area and if time permits we will talk about an approximation algorithm for MinHOM(H).