2020/09/24 by Piecyk, Marta, Rzążewski, Paweł · 1 citation
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2009.11642
For graphs G,H, a homomorphism from G to H is an edge-preserving mapping from V(G) to V(H). In the list homomorphism problem, denoted by LHom(H), we are given a graph G and lists L: V(G) → 2V(H), and we ask for a homomorphism from G to H which additionally respects the lists L. Very recently Okrasa, Piecyk, and Rzążewski [ESA 2020] defined an invariant i^*(H) and proved that under the SETH O^* (i^*(H)^\textrmtw(G)) is the tight complexity bound for LHom(H), parameterized by the treewidth \textrmtw(G) of the instance graph G. We study the complexity of the problem under dirretent parameterizations. As the first result, we show that i^*(H) is also the right complexity base if the parameter is the size of a minimum feedback vertex set of G. Then we turn our attention to a parameterization by the cutwidth \textrmctw(G) of G. Jansen and Nederlof~[ESA 2018] showed that List k-Coloring (i.e., LHom(Kk)) can be solved in time O^* (c^\textrmctw(G)) where c does not depend on k. Jansen asked if this behavior extends to graph homomorphisms. As the main result of the paper, we answer the question in the negative. We define a new graph invariant mim^*(H) and prove that LHom(H) problem cannot be solved in time O^* ((mim^*(H)-ε)^\textrmctw(G)) for any ε >0, unless the SETH fails. This implies that there is no c, such that for every odd cycle the non-list version of the problem can be solved in time O^* (c^\textrmctw(G) ). Finally, we generalize the algorithm of Jansen and Nederlof, so that it can be used to solve LHom(H) for every graph H; its complexity depends on \textrmctw(G) and another invariant of H, which is constant for cliques.