Fine-grained complexity of graph homomorphism for bounded cliquewidth

by Kirill Simonov (TU Wien)

Friday 26 Nov 2021, 12:00 → 14:00 Europe/Moscow

PDMI

For a fixed graph H, consider the graph homomorphism problem Hom(H), i.e. find an edge-preserving mapping from V(G) to V(H). Specifically, if H is the complete graph K_k, Hom(H) is equivalent to k-Coloring. Thus, even in this special case, the problem is NP-complete for each k ≥ 3, and it is also NP-complete for nearly all other graphs H.

Okrasa и Rzaͅżewski [SODA 2020] showed the following dichotomy for Hom(H) with respect to treewidth of G: Hom(H) can be solved in time |H|^tw(G) poly(|V(G)|), but for any ε > 0 there is no algorithm for Hom(H) with running time (|H| - ε)^tw(G) poly(|V(G)|), assuming SETH.
As stated, the result holds only if H is a projective core, however, a similar dichotomy follows for nearly all graphs. Moreover, assuming a long-standing hypothesis from algebraic graph theory, this classification covers all graphs H.

In this talk, we show a similar dichotomy with respect to cliquewidth of G. Cliquewidth, similarly to treewidth, is a structural width parameter of the graph, albeit a more general one: cliquewidth is always bounded when treewidth is bounded, but also for other dense graph classes, e.g. cliques. The conditions under which the dichotomy is given repeat the conditions obtained for treewidth, however, the precise running time-bound is f(H)^cw(G) poly(|V(G)|), where cw(G) is the cliquewidth of G, and f(H) is a certain structural parameter of H, specifically the number of distinct open neighborhoods of subsets of V(H).

This is a joint work with Robert Ganian, Thekla Hamm, Viktoria Korchemna and Karolina Okrasa.