Marta Piecyk
supervisor: Zbigniew Lonc, Paweł Rzążewski
A homomorphism f from a graph G=(V(G),E(G)) to a graph H=(V(H),E(H)) is an edge-preserving mapping from V(G) to V(H), i.e., for every edge uv of G, it holds that f(u)f(v) is an edge of H.
For a fixed graph H, in the Graph Homomorphism problem, denoted by Hom(H), we are given a graph G, and the task is to determine, whether there is a homomorphism from G to H.
One of the well known variants of Hom(H) is the List Homomorphism problem, denoted by LHom(H). In the LHom(H) problem, the graph G is given along with the lists L: V(G)->2^V(H), and the task is to determine, if there exists a homomorphism f from G to H, which additionally respects lists L, i.e., for every v in V(G) it holds that f(v) is in L(v).
Hom(H) and LHom(H) have been widely studied and their computational complexity - in classical sense of being polynomial-time solvable or NP-hard - has been fully classified (Hell & Nešetril, Feder & Hell & Huang).
In my talk I will focus on NP-hard cases of those problems, i.e., cases that we belive cannot be solved in polynomial time.
I will show how the complexity of the problems depends on some structural parameters of the input graph G.