Key points are not available for this paper at this time.
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 \ (s (H) \) and show that for each \ (H\), the homomorphism problem can be solved in time \ (O^* (s (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.
Ganian et al. (Mon,) studied this question.