Report
The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width
| العنوان: | The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width |
|---|---|
| المؤلفون: | Ganian, Robert, Hamm, Thekla, Korchemna, Viktoriia, Okrasa, Karolina, Simonov, Kirill |
| سنة النشر: | 2022 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Computational Complexity, 68R10, G.2.2 |
| الوصف: | 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. Comment: 21 pages, 2 figures. arXiv admin note: text overlap with arXiv:1804.07975 by other authors |
| نوع الوثيقة: | Working Paper |
| DOI: | 10.4230/LIPIcs.ICALP.2022.66 |
| URL الوصول: | http://arxiv.org/abs/2210.06845 |
| رقم الانضمام: | edsarx.2210.06845 |
| قاعدة البيانات: | arXiv |
| DOI: | 10.4230/LIPIcs.ICALP.2022.66 |
|---|