Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.66
URN: urn:nbn:de:0030-drops-164076
URL: https://drops.dagstuhl.de/opus/volltexte/2022/16407/
Ganian, Robert ; Hamm, Thekla ; Korchemna, Viktoriia ; Okrasa, Karolina ; Simonov, Kirill
The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{ganian_et_al:LIPIcs.ICALP.2022.66,
author = {Ganian, Robert and Hamm, Thekla and Korchemna, Viktoriia and Okrasa, Karolina and Simonov, Kirill},
title = {{The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {66:1--66:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-235-8},
ISSN = {1868-8969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16407},
URN = {urn:nbn:de:0030-drops-164076},
doi = {10.4230/LIPIcs.ICALP.2022.66},
annote = {Keywords: homomorphism, clique-width, fine-grained complexity}
}
| Keywords: | homomorphism, clique-width, fine-grained complexity | |
| Seminar: | 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 28.06.2022 |
