Karolina Okrasa

Politechnika Warszawska

Dla dwóch grafów G i H, homomorfizmem G w H nazywamy funkcję f ze zbioru wierzchołków G w zbiór wierzchołków H, taką że jeśli uv jest krawędzią w G, to f(u)f(v) jest krawędzią w H. Homomorfizmy grafów są naturalnym uogólnieniem problemu kolorowania grafów, jednego z najlepiej zbadanych problemów grafowych.

Opowiem o obliczeniowych aspektach problemu homomorfizmu grafów: dla ustalonego grafu H, mając dany graf G jako instancję wejściową, jak szybko jesteśmy w stanie odpowiedzieć na pytanie czy istnieje homomorfizm G w H — oraz, co w tym kontekście znaczy: „szybko”?

W ogólności problem homomorfizmu jest NP-zupełny; oznacza to, między innymi, że nie znamy algorytmu, który stwierdza, czy dla grafu G o n wierzchołkach istnieje homomorfizm z G w H, i jednocześnie działa w czasie wielomianowym względem n.

Z tego powodu interesuje nas, jakie dodatkowe założenia na klasę instancji wejściowych mogą pomóc w konstruowaniu efektywnych algorytmów.

Podczas referatu skupimy się na tzw. dziedzicznych klasach grafów, czyli klasach zamkniętych na operację usuwania wierzchołków. Każdą taką klasę grafów można równoważnie zdefiniować zabraniając pewnej ustalonej rodziny podgrafów indukowanych.

Przedstawię wyniki uzyskanie wspólnie z Pawłem Rzążewskim.

Wykład odbędzie się 9 maja 2023 o godzinie 17.00 przy użyciu komunikatora Zoom.