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)$. In the graph homomorphism problem, denoted by $Hom(H)$,the graph $H$ is fixed and we need to determine if there exists a homomorphismfrom an instance graph $G$ to $H$. We study the complexity of the problemparameterized by the cutwidth of $G$.  We aim, for each $H$, for algorithms for $Hom(H)$ running in time $c_H^kn^{\mathcal{O}(1)}$ and matching lower bounds that exclude $c_H^{k \cdoto(1)}n^{\mathcal{O}(1)}$ or $c_H^{k(1-\Omega(1))}n^{\mathcal{O}(1)}$ timealgorithms under the (Strong) Exponential Time Hypothesis.  In the paper we introduce a new parameter that we call $\mathrm{mimsup}(H)$.Our main contribution is strong evidence of a close connection between $c_H$and $\mathrm{mimsup}(H)$:  * an information-theoretic argument that the number of states needed in anatural dynamic programming algorithm is at most $\mathrm{mimsup}(H)^k$,  * lower bounds that show that for almost all graphs $H$ indeed we have $c_H\geq \mathrm{mimsup}(H)$, assuming the (Strong) Exponential-Time Hypothesis,and  * an algorithm with running time $\exp ( {\mathcal{O}( \mathrm{mimsup}(H)\cdot k \log k)}) n^{\mathcal{O}(1)}$.  The parameter $\mathrm{mimsup}(H)$ can be thought of as the $p$-th root ofthe maximum induced matching number in the graph obtained by multiplying $p$copies of $H$ via certain graph product, where $p$ tends to infinity. It canalso be defined as an asymptotic rank parameter of the adjacency matrix of $H$.Our results tightly link the parameterized complexity of a problem to such anasymptotic rank parameter for the first time.

Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Rank Parameters