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

We consider a generalization of finding a homomorphism from an input digraph$G$ to a fixed digraph $H$, HOM($H$). In this setting, we are given an inputdigraph $G$ together with a list function from $G$ to $2^H$. The goal is tofind a homomorphism from $G$ to $H$ with respect to the lists if one exists.  We show that if the list function is a Maltsev polymorphism then decidingwhether $G$ admits a homomorphism to $H$ is polynomial time solvable. In ourapproach, we only use the existence of the Maltsev polymorphism. Furthermore,we show that deciding whether a relational structure $\mathcal{R}$ admits aMaltsev polymorphism is a special case of finding a homormphism from a graph$G$ to a graph $H$ and a list function with a Maltsev polymorphism. Since theexistence of Maltsev is not required in our algorithm, we can decide inpolynomial time whether the relational structure $\mathcal{R}$ admits Maltsevor not.  We also discuss forbidden obstructions for the instances admitting Maltsevlist polymorphism. We have implemented our algorithm and tested on instancesarising from linear equations, and other types of instances.

Digraphs Homomorphism Problems with Maltsev Condition