论文标题
图形宽度参数的图形同态的细粒度复杂性
The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width
论文作者
论文摘要
通用同态问题询问输入图$ g $是否在文献中广泛研究了固定目标图$ h $的同构$ g $。在本文中，我们提供了$ g $（表示$ \ permatatorName {cw} $）的同构问题的运行时间的细粒度复杂性分类，用于在强大的指数时间假设下几乎所有$ h $的选择。特别是，我们确定了$ h $的属性，称为签名数字$ s（h）$，并表明对于每个$ h $，可以在$ \ mathcal {o}^*（s（h）^{\ propatatorNareame {cw}}}}}）$的时间内解决同态问题。至关重要的是，我们证明该算法可用于获得基本紧密的上限。具体而言，我们提供了一个减少功能，可为每个$ h $提供匹配的下限，该$ h $是投影核心或图形，该图形构成具有其他属性的分解 - 使我们能够在长期存在的猜想下涵盖所有可能的目标图。
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 $\operatorname{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 $\mathcal{O}^*(s(H)^{\operatorname{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.
