Seminar: The Graph Homomorphism Problem and its Applications
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
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).