Ganian, R., Hamm, T., Korchemna, V., Okrasa, K., & Simonov, K. (2024). The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width. ACM Transactions on Algorithms, 20(3). https://doi.org/10.1145/3652514
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. In this article, we provide a fine-grained complexity classification of the running time of the homomorphism problem with respect to the clique-width of G (denoted cw) for virtually all choices of H under the Strong Exponential Time Hypothesis. In particular, we identify a property of H called the signature number B(H) and show that for each H, the homomorphism problem can be solved in time O∗(B(H)cw). Crucially, we then show that this algorithm can be used to obtain essentially tight upper bounds. Specifically, 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.
