<div class="csl-bib-body">
<div class="csl-entry">Ganian, R., Hamm, T., Korchemna, V., Okrasa, K., & Simonov, K. (2022). The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width. In <i>49th EATCS International Conference on Automata, Languages, and Programming</i> (pp. 66:1-66:20). Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH. https://doi.org/10.4230/LIPIcs.ICALP.2022.66</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/135877
-
dc.description.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.
en
dc.description.sponsorship
Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
dc.description.sponsorship
Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
dc.language.iso
en
-
dc.relation.ispartofseries
Leibniz international proceedings in informatics
-
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
-
dc.subject
clique-width
en
dc.subject
fine-grained complexity
en
dc.subject
homomorphism
en
dc.title
The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width