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).