Skip to content

Monday 11:30 – Kirill Simonov

The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width

The generic homomorphism problem, which asks whether an input graph \(G\) admits a homomorphism into a fixed target graph \(H\), has been widely studied in the literature. We provide a fine-grained complexity classification of the running time of the homomorphism problem with respect to the clique-width of \(G\) for virtually all choices of \(H\) under the Strong Exponential Time Hypothesis. In particular, we identify a property of H called the signature number \(s(H)\) and show that for each \(H\) the homomorphism problem can be solved in time \(O^\ast(s(H)^{cw})\). Crucially, we then show that this algorithm is essentially optimal. We provide a reduction that yields matching lower bounds for each \(H\) that is either a projective core or a graph admitting a factorization with additional properties—allowing us to cover all possible target graphs under long-standing conjectures.