Marta Piecyk
supervisor: Zbigniew Lonc
For a fixed graph H, in the graph homomorphism problem, denoted by Hom(H), we are given a graph G and we have to determine, if there exists a homomorphism from G to H, i.e., an edge-preserving mapping f: V(G) -> V(H). In the list version of the problem, denoted by LHom(H), the graph G is given along with lists L: V(G) -> 2^V(H), and we ask if there exists a homomorphism f from G to H that additionally respects lists, i.e., for every v in V(G) we have that f(v) in L(v). Let us note that the graph homomorphism problem is a generalization of the well-known k-coloring problem.
For many graph parameters t(G), the typical behavior is as follows. There is an algorithm solving k-coloring in time k^t(G)* |G|^O(1) and this running time cannot be even slightly improved under standard complexity assumptions. This is not the case for a parameter called cutwidth, denoted by ctw(G). Jansen and Nederlof [TCS 2019] provided a randomized algorithm that solves k-coloring in time 2^ctw(G) * |G|^O(1), and a deterministic one with running time 2^(omega* ctw(G))*|G|^O(1), where omega is the matrix multiplication constant.
A natural question is if this behavior can be extended to a more general problem, i.e., (list) homomorphisms. It appears that there is no constant c such that for every H, the Hom(H) problem can be solved in time c^ctw(G)*|G|^O(1). In my poster I will show more details of this result.
Joint work with P. Dvořak, C. Groenland, I. Mannes, J. Nederlof, and P. Rzążewski.