English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

A homomorphism from a graph $G$ to a graph $H$ is an edge-preserving mappingfrom $V(G)$ to $V(H)$. Let $H$ be a fixed graph with possible loops. In thelist homomorphism problem, denoted by LHom($H$), we are given a graph $G$,whose every vertex $v$ is assigned with a list $L(v)$ of vertices of $H$. Weask whether there exists a homomorphism $h$ from $G$ to $H$, which respectslists $L$, i.e., for every $v \in V(G)$ it holds that $h(v) \in L(v)$.  The complexity dichotomy for LHom($H$) was proven by Feder, Hell, and Huang[JGT 2003]. We are interested in the complexity of the problem, parameterizedby the treewidth of the input graph. This problem was investigated by Egri,Marx, and Rz\k{a}\.zewski [STACS 2018], who obtained tight complexity boundsfor the special case of reflexive graphs $H$.  In this paper we extend and generalize their results for \emph{all} relevantgraphs $H$, i.e., those, for which the LHom{H} problem is NP-hard. For everysuch $H$ we find a constant $k = k(H)$, such that LHom($H$) on instances with$n$ vertices and treewidth $t$  * can be solved in time $k^{t} \cdot n^{\mathcal{O}(1)}$, provided that theinput graph is given along with a tree decomposition of width $t$,  * cannot be solved in time $(k-\varepsilon)^{t} \cdot n^{\mathcal{O}(1)}$,for any $\varepsilon >0$, unless the SETH fails.  For some graphs $H$ the value of $k(H)$ is much smaller than the trivialupper bound, i.e., $|V(H)|$.  Obtaining matching upper and lower bounds shows that the set of algorithmictools we have discovered cannot be extended in order to obtain fasteralgorithms for LHom($H$) in bounded-treewidth graphs. Furthermore, neither thealgorithm, nor the proof of the lower bound, is very specific to treewidth. Webelieve that they can be used for other variants of LHom($H$), e.g. withdifferent parameterizations.

Full complexity classification of the list homomorphism problem for bounded-treewidth graphs