Воскресенье 26.12. Kirill Simonov (University of Bergen): "Fine-grained complexity of graph homomorphism for bounded cliquewidth"
PDMI seminars
Тема: Fine-grained complexity of graph homomorphism for bounded cliquewidth
Место: PDMI & Zoom (hybrid format)
Время: 26.12.2021, 12:00
Докладчик: Kirill Simonov (University of Bergen)
Abstract:
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 dichotome follows for nearly all graphs. Moreover, assuming a long-standing hypothesis from algebraic graph theory, this classsification 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 repear the conditions obtained for treewidth, however the preciese 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.
Dmitry M. Itsykson
--
Вы получили это сообщение, поскольку подписаны на группу "spb-complexity".
Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес spb-complexit...@googlegroups.com.
Чтобы посмотреть обсуждение на веб-странице, перейдите по ссылке https://groups.google.com/d/msgid/spb-complexity/00000000000048b33405d1634f1f%40google.com.
