Graph homomorphism problem parameterized by cutwidth

Speaker(s)

Marta Piecyk

Language of the talk

English

Date

March 21, 2025, 2:15 p.m.

Room

room 5060

Seminar

Seminar Algorithms

---

For a fixed (target) graph H, in the graph homomorphism problem, denoted by Hom(H), we are given a graph G, and we have to determine whether there exists an edge preserving mapping f: V(G)-> V(H). This problem is a generalization of the well-studied k-Coloring.

For a linear ordering v_1,...,v_n of vertices of a graph G, the width of the ordering is the maximum number of edges from {v_1,...,v_i} to {v_{i+1},...,v_n} over all i. The cutwidth of G, denoted by ctw(G), is the minimum width over all linear orderings of V(G).

Jansen and Nederlof [TCS, 2019] proved that every instance G of k-Coloring can be solved in (randomized) time 2^{ctw(G)}*|G|^{O(1)}. This is very uncommon, as usually, for many graph parameters t(G), the optimal running time of an algorithm solving k-Coloring is f(k)^{t(G)}*|G|^{O(1)}, where f is some increasing function of k.

A natural question is how far the phenomenon of k-Coloring parameterized by cutwidth can be generalized.
We try to find, for every H, a constant c_H such that we can solve every instance G of Hom(H) in time c_H^{ctw(G)}*|G|^{O(1)}, but there is no algorithm with running time (c_H-\epsilon)^{ctw(G)}*|G|^{O(1)} for any \epsilon>0, unless the SETH fails.
We define an asymptotic parameter, called mimsup(H), which is closely related to the sizes of maximum induced matchings in powers of H (with respect to direct product) and we give strong evidence that c_H=mimsup(H).

This is joint work with Carla Groenland, Isja Mannens, Jesper Nederlof, and Paweł Rzążewski.

---